Bagaimana saya bisa tahu jika sebuah string berulang dengan Python?

Saya sedang mencari cara untuk menguji apakah suatu string diberikan berulang untuk seluruh string atau tidak.

Contoh:

[
    '0045662100456621004566210045662100456621',             # '00456621'
    '0072992700729927007299270072992700729927',             # '00729927'
    '001443001443001443001443001443001443001443',           # '001443'
    '037037037037037037037037037037037037037037037',        # '037'
    '047619047619047619047619047619047619047619',           # '047619'
    '002457002457002457002457002457002457002457',           # '002457'
    '001221001221001221001221001221001221001221',           # '001221'
    '001230012300123001230012300123001230012300123',        # '00123'
    '0013947001394700139470013947001394700139470013947',    # '0013947'
    '001001001001001001001001001001001001001001001001001',  # '001'
    '001406469760900140646976090014064697609',              # '0014064697609'
]

adalah string yang berulang, dan

[
    '004608294930875576036866359447',
    '00469483568075117370892018779342723',
    '004739336492890995260663507109',
    '001508295625942684766214177978883861236802413273',
    '007518796992481203',
    '0071942446043165467625899280575539568345323741',
    '0434782608695652173913',
    '0344827586206896551724137931',
    '002481389578163771712158808933',
    '002932551319648093841642228739',
    '0035587188612099644128113879',
    '003484320557491289198606271777',
    '00115074798619102416570771',
]

adalah contoh yang tidak.

Bagian berulang dari string yang saya berikan bisa sangat panjang, dan string itu sendiri bisa 500 atau lebih karakter, jadi perulangan melalui setiap karakter mencoba membangun pola kemudian memeriksa pola vs sisa string tampaknya sangat lambat. Lipat gandakan dengan ratusan string dan saya tidak bisa melihat solusi intuitif.

Saya telah melihat ke regex sedikit dan mereka tampak bagus ketika Anda tahu apa yang Anda cari, atau setidaknya panjang pola yang Anda cari. Sayangnya, saya juga tidak tahu.

Bagaimana saya bisa tahu apakah sebuah string berulang dan jika ya, apa yang merupakan pengulangan terpendek adalah?

Berikut adalah solusi ringkas yang menghindari ekspresi reguler dan loop in-Python lambat:

def principal_period(s):
    i = (s+s).find(s, 1, -1)
    return None if i == -1 else s[:i]

Lihat jawaban Wiki Komunitas yang dimulai oleh @davidism untuk hasil benchmark. Singkatnya,

Solusi David Zhang adalah pemenang yang jelas, mengungguli semua yang lain dengan setidaknya 5x untuk set contoh besar.

(Kata-kata jawaban itu, bukan milikku.)

Ini didasarkan pada pengamatan bahwa string adalah periodik jika dan hanya jika sama dengan rotasi nontrivial itu sendiri. Kudos to @AleksiTorhamo karena menyadari bahwa kita dapat memulihkan periode pokok dari indeks kejadian pertama sin (s+s)[1:-1], dan untuk memberi tahu saya tentang opsionalstart dan endargumen Python string.find.

Berikut ini solusi menggunakan ekspresi reguler.

import re

REPEATER = re.compile(r"(.+?)\1+$")

def repeated(s):
    match = REPEATER.match(s)
    return match.group(1) if match else None

Mengulangi contoh-contoh dalam pertanyaan:

examples = [
    '0045662100456621004566210045662100456621',
    '0072992700729927007299270072992700729927',
    '001443001443001443001443001443001443001443',
    '037037037037037037037037037037037037037037037',
    '047619047619047619047619047619047619047619',
    '002457002457002457002457002457002457002457',
    '001221001221001221001221001221001221001221',
    '001230012300123001230012300123001230012300123',
    '0013947001394700139470013947001394700139470013947',
    '001001001001001001001001001001001001001001001001001',
    '001406469760900140646976090014064697609',
    '004608294930875576036866359447',
    '00469483568075117370892018779342723',
    '004739336492890995260663507109',
    '001508295625942684766214177978883861236802413273',
    '007518796992481203',
    '0071942446043165467625899280575539568345323741',
    '0434782608695652173913',
    '0344827586206896551724137931',
    '002481389578163771712158808933',
    '002932551319648093841642228739',
    '0035587188612099644128113879',
    '003484320557491289198606271777',
    '00115074798619102416570771',
]

for e in examples:
    sub = repeated(e)
    if sub:
        print("%r: %r" % (e, sub))
    else:
        print("%r does not repeat." % e)

... menghasilkan keluaran ini:

'0045662100456621004566210045662100456621': '00456621'
'0072992700729927007299270072992700729927': '00729927'
'001443001443001443001443001443001443001443': '001443'
'037037037037037037037037037037037037037037037': '037'
'047619047619047619047619047619047619047619': '047619'
'002457002457002457002457002457002457002457': '002457'
'001221001221001221001221001221001221001221': '001221'
'001230012300123001230012300123001230012300123': '00123'
'0013947001394700139470013947001394700139470013947': '0013947'
'001001001001001001001001001001001001001001001001001': '001'
'001406469760900140646976090014064697609': '0014064697609'
'004608294930875576036866359447' does not repeat.
'00469483568075117370892018779342723' does not repeat.
'004739336492890995260663507109' does not repeat.
'001508295625942684766214177978883861236802413273' does not repeat.
'007518796992481203' does not repeat.
'0071942446043165467625899280575539568345323741' does not repeat.
'0434782608695652173913' does not repeat.
'0344827586206896551724137931' does not repeat.
'002481389578163771712158808933' does not repeat.
'002932551319648093841642228739' does not repeat.
'0035587188612099644128113879' does not repeat.
'003484320557491289198606271777' does not repeat.
'00115074798619102416570771' does not repeat.

Ekspresi reguler (.+?)\1+$dibagi menjadi tiga bagian:

1. (.+?)adalah grup yang cocok yang mengandung setidaknya satu (tetapi sesedikit mungkin) karakter apa pun (karena +?tidak serakah ).

2. \1+ memeriksa setidaknya satu pengulangan dari kelompok yang cocok di bagian pertama.

3. $memeriksa akhir string, untuk memastikan bahwa tidak ada konten tambahan, yang tidak berulang setelah substring berulang (dan menggunakan re.match()memastikan bahwa tidak ada teks yang tidak berulang sebelum substring berulang).

Dalam Python 3.4 dan yang lebih baru, Anda bisa menjatuhkan $dan menggunakannya re.fullmatch()sebagai gantinya, atau (dalam Python apa pun setidaknya sejauh 2.3) pergi ke arah lain dan gunakan re.search()dengan regex ^(.+?)\1+$, yang semuanya lebih ke selera pribadi daripada yang lain.

Anda dapat membuat pengamatan bahwa agar sebuah string dianggap berulang, panjangnya harus dapat dibagi dengan panjang urutan berulangnya. Mengingat bahwa, di sini adalah solusi yang menghasilkan pembagi panjang dari 1ke n / 2inklusif, membagi string asli ke substring dengan panjang pembagi, dan menguji kesetaraan hasil set:

from math import sqrt, floor

def divquot(n):
    if n > 1:
        yield 1, n
    swapped = []
    for d in range(2, int(floor(sqrt(n))) + 1):
        q, r = divmod(n, d)
        if r == 0:
            yield d, q
            swapped.append((q, d))
    while swapped:
        yield swapped.pop()

def repeats(s):
    n = len(s)
    for d, q in divquot(n):
        sl = s[0:d]
        if sl * q == s:
            return sl
    return None

EDIT: Dalam Python 3, /operator telah berubah untuk melakukan pembagian float secara default. Untuk mendapatkan intpembagian dari Python 2, Anda bisa menggunakan //operator sebagai gantinya. Terima kasih kepada @ TigerhawkT3 untuk membawa ini menjadi perhatian saya.

The //Melakukan Operator bilangan bulat divisi di kedua Python 2 dan Python 3, jadi saya telah memperbarui jawaban untuk mendukung kedua versi. Bagian tempat kami menguji untuk melihat apakah semua substring sama sekarang adalah operasi hubung singkatall dan ekspresi generator.

UPDATE: Sebagai tanggapan terhadap perubahan dalam pertanyaan awal, kode sekarang telah diperbarui untuk mengembalikan substring berulang terkecil jika ada dan Nonejika tidak. @ godlygeek telah menyarankan penggunaan divmoduntuk mengurangi jumlah iterasi pada divisorsgenerator, dan kode telah diperbarui agar sesuai dengan itu juga. Sekarang mengembalikan semua pembagi positif ndalam urutan menaik, eksklusif untuk ndirinya sendiri.

Pembaruan lebih lanjut untuk kinerja tinggi: Setelah beberapa pengujian, saya sampai pada kesimpulan bahwa hanya menguji kesetaraan string memiliki kinerja terbaik dari semua solusi pengiris atau iterator dengan Python. Dengan demikian, saya telah mengambil daun dari buku @ TigerhawkT3 dan memperbarui solusi saya. Sekarang lebih dari 6x lebih cepat dari sebelumnya, terutama lebih cepat dari solusi Tigerhawk tetapi lebih lambat dari David.

Berikut adalah beberapa tolok ukur untuk berbagai jawaban untuk pertanyaan ini. Ada beberapa hasil yang mengejutkan, termasuk kinerja yang sangat berbeda tergantung pada string yang diuji.

Beberapa fungsi dimodifikasi untuk bekerja dengan Python 3 (terutama dengan mengganti /dengan //untuk memastikan pembagian integer). Jika Anda melihat sesuatu yang salah, ingin menambahkan fungsi Anda, atau ingin menambahkan string uji lain, ping @ZeroPiraeus di chatroom Python .

Singkatnya: ada sekitar 50x perbedaan antara solusi terbaik dan berkinerja terburuk untuk sekumpulan besar contoh data yang disediakan oleh OP di sini (melalui komentar ini ). Solusi David Zhang adalah pemenang yang jelas, mengungguli semua yang lain sekitar 5x untuk set contoh besar.

Beberapa jawaban sangat lambat dalam kasus "tidak cocok" yang sangat besar. Kalau tidak, fungsinya tampaknya sama-sama cocok atau jelas pemenang tergantung pada tes.

Berikut adalah hasilnya, termasuk plot yang dibuat menggunakan matplotlib dan seaborn untuk menunjukkan distribusi yang berbeda:

Corpus 1 (contoh yang disediakan - set kecil)

mean performance:
 0.0003  david_zhang
 0.0009  zero
 0.0013  antti
 0.0013  tigerhawk_2
 0.0015  carpetpython
 0.0029  tigerhawk_1
 0.0031  davidism
 0.0035  saksham
 0.0046  shashank
 0.0052  riad
 0.0056  piotr

median performance:
 0.0003  david_zhang
 0.0008  zero
 0.0013  antti
 0.0013  tigerhawk_2
 0.0014  carpetpython
 0.0027  tigerhawk_1
 0.0031  davidism
 0.0038  saksham
 0.0044  shashank
 0.0054  riad
 0.0058  piotr

Corpus 2 (contoh disediakan - set besar)

mean performance:
 0.0006  david_zhang
 0.0036  tigerhawk_2
 0.0036  antti
 0.0037  zero
 0.0039  carpetpython
 0.0052  shashank
 0.0056  piotr
 0.0066  davidism
 0.0120  tigerhawk_1
 0.0177  riad
 0.0283  saksham

median performance:
 0.0004  david_zhang
 0.0018  zero
 0.0022  tigerhawk_2
 0.0022  antti
 0.0024  carpetpython
 0.0043  davidism
 0.0049  shashank
 0.0055  piotr
 0.0061  tigerhawk_1
 0.0077  riad
 0.0109  saksham

Corpus 3 (kasus tepi)

mean performance:
 0.0123  shashank
 0.0375  david_zhang
 0.0376  piotr
 0.0394  carpetpython
 0.0479  antti
 0.0488  tigerhawk_2
 0.2269  tigerhawk_1
 0.2336  davidism
 0.7239  saksham
 3.6265  zero
 6.0111  riad

median performance:
 0.0107  tigerhawk_2
 0.0108  antti
 0.0109  carpetpython
 0.0135  david_zhang
 0.0137  tigerhawk_1
 0.0150  shashank
 0.0229  saksham
 0.0255  piotr
 0.0721  davidism
 0.1080  zero
 1.8539  riad

Tes dan hasil mentah tersedia di sini .

Solusi non-regex:

def repeat(string):
    for i in range(1, len(string)//2+1):
        if not len(string)%len(string[0:i]) and string[0:i]*(len(string)//len(string[0:i])) == string:
            return string[0:i]

Solusi non-regex yang lebih cepat, terima kasih kepada @ThatWeirdo (lihat komentar):

def repeat(string):
    l = len(string)
    for i in range(1, len(string)//2+1):
        if l%i: continue
        s = string[0:i]
        if s*(l//i) == string:
            return s

Solusi di atas sangat jarang lebih lambat daripada yang asli dengan beberapa persen, tetapi biasanya sedikit lebih baik - kadang-kadang jauh lebih cepat. Ini masih tidak lebih cepat dari davidism untuk string yang lebih panjang, dan solusi regex nol lebih unggul untuk string pendek. Itu keluar ke tercepat (menurut tes davidisme di github - lihat jawabannya) dengan string sekitar 1000-1500 karakter. Apapun, itu tercepat tercepat (atau lebih baik) dalam semua kasus yang saya uji. Terima kasih, ThatWeirdo.

Uji:

print(repeat('009009009'))
print(repeat('254725472547'))
print(repeat('abcdeabcdeabcdeabcde'))
print(repeat('abcdefg'))
print(repeat('09099099909999'))
print(repeat('02589675192'))

Hasil:

009
2547
abcde
None
None
None

Pertama, membagi dua string selama itu duplikat "2 bagian". Ini mengurangi ruang pencarian jika ada jumlah yang berulang. Kemudian, bekerja ke depan untuk menemukan string berulang terkecil, periksa apakah memisahkan string penuh dengan semakin besar sub-string menghasilkan hanya nilai-nilai kosong. Hanya sub-string yang length // 2perlu diuji karena apa pun yang tidak akan berulang.

def shortest_repeat(orig_value):
    if not orig_value:
        return None

    value = orig_value

    while True:
        len_half = len(value) // 2
        first_half = value[:len_half]

        if first_half != value[len_half:]:
            break

        value = first_half

    len_value = len(value)
    split = value.split

    for i in (i for i in range(1, len_value // 2) if len_value % i == 0):
        if not any(split(value[:i])):
            return value[:i]

    return value if value != orig_value else None

Ini mengembalikan kecocokan terpendek atau Tidak ada jika tidak ada kecocokan.

Masalahnya juga dapat diselesaikan dalam O(n)kasus terburuk dengan fungsi awalan.

Catatan, mungkin lebih lambat dalam kasus umum (UPD: dan jauh lebih lambat) dibandingkan solusi lain yang tergantung pada jumlah pembagi dari n, tetapi biasanya menemukan gagal cepat, saya pikir salah satu kasus buruk bagi mereka akan aaa....aab, di mana ada n - 1 = 2 * 3 * 5 * 7 ... *p_n - 1 a's

Pertama-tama Anda perlu menghitung fungsi awalan

def prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in xrange(1, n):
        j = pi[i - 1]
        while(j > 0 and s[i] != s[j]):
            j = pi[j - 1]
        if (s[i] == s[j]):
            j += 1
        pi[i] = j;
    return pi

maka baik tidak ada jawaban atau periode terpendek adalah

k = len(s) - prefix_function(s[-1])

dan Anda hanya perlu memeriksa apakah k != n and n % k == 0(jika k != n and n % k == 0jawabannya adalah s[:k], kalau tidak, tidak ada jawaban

Anda dapat memeriksa buktinya di sini (dalam bahasa Rusia, tetapi penerjemah online mungkin akan melakukan triknya)

def riad(s):
    n = len(s)
    pi = [0] * n
    for i in xrange(1, n):
        j = pi[i - 1]
        while(j > 0 and s[i] != s[j]):
            j = pi[j - 1]
        if (s[i] == s[j]):
            j += 1
        pi[i] = j;
    k = n - pi[-1]
    return s[:k] if (n != k and n % k == 0) else None

Versi ini hanya mencoba panjang urutan kandidat yang merupakan faktor dari panjang string; dan menggunakan *operator untuk membangun string full-length dari urutan kandidat:

def get_shortest_repeat(string):
    length = len(string)
    for i in range(1, length // 2 + 1):
        if length % i:  # skip non-factors early
            continue

        candidate = string[:i]
        if string == candidate * (length // i):
            return candidate

    return None

Terima kasih kepada TigerhawkT3 karena memperhatikan bahwa length // 2tanpa + 1akan gagal untuk mencocokkan ababkasus ini.

Inilah solusi lurus ke depan, tanpa regex.

Untuk substring smulai dari indeks nol, dengan panjang 1 hingga len(s), periksa apakah substring itu, substradalah pola yang berulang. Pemeriksaan ini dapat dilakukan dengan menggabungkan substrdengan ratiowaktu itu sendiri , sehingga panjang string yang dibentuk sama dengan panjang s. Karenanyaratio=len(s)/len(substr) .

Kembali saat substring pertama ditemukan. Ini akan memberikan substring sekecil mungkin, jika ada.

def check_repeat(s):
    for i in range(1, len(s)):
        substr = s[:i]
        ratio = len(s)/len(substr)
        if substr * ratio == s:
            print 'Repeating on "%s"' % substr
            return
    print 'Non repeating'

>>> check_repeat('254725472547')
Repeating on "2547"
>>> check_repeat('abcdeabcdeabcdeabcde')
Repeating on "abcde"

Saya mulai dengan lebih dari delapan solusi untuk masalah ini. Beberapa didasarkan pada regex (match, findall, split), beberapa slicing string dan pengujian, dan beberapa dengan metode string (find, count, split). Masing-masing memiliki manfaat dalam kejelasan kode, ukuran kode, kecepatan dan konsumsi memori. Saya akan memposting jawaban saya di sini ketika saya perhatikan bahwa kecepatan eksekusi diperingkat penting, jadi saya melakukan lebih banyak pengujian dan peningkatan untuk sampai pada ini:

def repeating(s):
    size = len(s)
    incr = size % 2 + 1
    for n in xrange(1, size//2+1, incr):
        if size % n == 0:
            if s[:n] * (size//n) == s:
                return s[:n]

Jawaban ini tampaknya mirip dengan beberapa jawaban lain di sini, tetapi memiliki beberapa optimisasi kecepatan yang belum digunakan orang lain:

• xrange sedikit lebih cepat dalam aplikasi ini,
• jika string input adalah panjang ganjil, jangan periksa substring panjang genap,
• dengan menggunakan s[:n]secara langsung, kami menghindari membuat variabel di setiap loop.

Saya akan tertarik untuk melihat bagaimana kinerjanya dalam tes standar dengan perangkat keras umum. Saya percaya itu akan kekurangan algoritma David Zhang yang sangat baik dalam sebagian besar tes, tetapi seharusnya cukup cepat jika tidak.

Saya menemukan masalah ini sangat kontra-intuitif. Solusi yang saya pikir akan cepat lambat. Solusi yang tampak lambat itu cepat! Tampaknya penciptaan string Python dengan operator multiply dan perbandingan string sangat dioptimalkan.

Fungsi ini berjalan sangat cepat (diuji dan ini lebih dari 3 kali lebih cepat daripada solusi tercepat di sini pada string dengan lebih dari 100 ribu karakter dan perbedaannya semakin besar semakin lama pola pengulangannya). Mencoba meminimalkan jumlah perbandingan yang diperlukan untuk mendapatkan jawaban:

def repeats(string):
    n = len(string)
    tried = set([])
    best = None
    nums = [i for i in  xrange(2, int(n**0.5) + 1) if n % i == 0]
    nums = [n/i for i in nums if n/i!=i] + list(reversed(nums)) + [1]
    for s in nums:
        if all(t%s for t in tried):
            print 'Trying repeating string of length:', s
            if string[:s]*(n/s)==string:
                best = s
            else:
                tried.add(s)
    if best:
        return string[:best]

Perhatikan bahwa misalnya untuk string dengan panjang 8 ia hanya memeriksa fragmen ukuran 4 dan tidak perlu menguji lebih lanjut karena pola panjang 1 atau 2 akan menghasilkan pola berulang panjang 4:

>>> repeats('12345678')
Trying repeating string of length: 4
None

# for this one we need only 2 checks 
>>> repeats('1234567812345678')
Trying repeating string of length: 8
Trying repeating string of length: 4
'12345678'

Dalam jawaban David Zhang jika kita memiliki semacam penyangga bundar, ini tidak akan berfungsi: principal_period('6210045662100456621004566210045662100456621')karena permulaannya 621, di mana saya ingin meludahkannya:00456621 .

Memperluas solusinya, kita dapat menggunakan yang berikut:

def principal_period(s):
    for j in range(int(len(s)/2)):
        idx = (s[j:]+s[j:]).find(s[j:], 1, -1)
        if idx != -1:
            # Make sure that the first substring is part of pattern
            if s[:j] == s[j:][:idx][-j:]:
                break

    return None if idx == -1 else s[j:][:idx]

principal_period('6210045662100456621004566210045662100456621')
>>> '00456621'

Berikut ini adalah kode dalam python yang memeriksa pengulangan sub string dalam string utama yang diberikan oleh pengguna .

print "Enter a string...."
#mainstring = String given by user
mainstring=raw_input(">")
if(mainstring==''):
    print "Invalid string"
    exit()
#charlist = Character list of mainstring
charlist=list(mainstring)
strarr=''
print "Length of your string :",len(mainstring)
for i in range(0,len(mainstring)):
    strarr=strarr+charlist[i]
    splitlist=mainstring.split(strarr)
    count = 0
    for j in splitlist:
        if j =='':
            count+=1
    if count == len(splitlist):
        break
if count == len(splitlist):
    if count == 2:
        print "No repeating Sub-String found in string %r"%(mainstring)

    else:
        print "Sub-String %r repeats in string %r"%(strarr,mainstring)
else :
    print "No repeating Sub-String found in string %r"%(mainstring)

Masukan :

0045662100456621004566210045662100456621

Keluaran :

Panjang tali Anda: 40

Sub-String '00456621' berulang dalam string '0045662100456621004566210045662100456621'

Masukan :

004608294930875576036866359447

Keluaran :

Panjang tali Anda: 30

Tidak ditemukan Sub-String berulang dalam string '004608294930875576036866359447'