Pencocokan Pola String Tidak Diketahui

Saya ingin menentukan pola yang tidak diketahui dalam sebuah string seperti,

s=112468112468112468112468112468.

Jadi pada string ini, kita dapat melihat dengan jelas bahwa 112468 adalah pola yang berulang. Saya mencari di Google sedikit untuk menemukan beberapa algoritma untuk membantu saya, tapi saya hanya bisa melihat algoritma yang menemukan pola tertentu dalam string seperti algoritma Boyer-Moore dll.

Apa yang saya lakukan sekarang untuk menemukan pola berulang yang tidak diketahui ini adalah,

for(i=0;i<Length of String;i++)
{
  for(j=i+1;j<Length of String;j++)
  {
    if(s[i]==s[j] && s[i+1]==s[j+1] && s[i+2]==s[j+2] && s[i+3]==s[j+3])
    {
       patternlength=j-i;

           for(k=i;k<j;k++)
           {
            pattern[k]=s[i+k]
           }
     }
   }
}

Meskipun ini berfungsi untuk string tertentu dengan menggunakan jendela perbandingan 4 literal, ini mungkin tidak berfungsi untuk string lainnya. Adakah yang tahu solusi yang lebih baik untuk ini.

Terima kasih


string pattern-recognition
person Goku    schedule 20.02.2012    source sumber
comment
Memiliki mesin yang mengidentifikasi pola apa pun dalam teks bukanlah masalah sepele. Apakah Anda hanya tertarik pada, misalnya, string dengan pola berulang? Jika Anda dapat memberi kami jenis atau pola atau pola yang ingin Anda telusuri, kami mungkin dapat membantu lebih lanjut.   -  person jefflunt    schedule 21.02.2012
comment
Jenis pola yang saya hadapi adalah string dengan pola berulang dan akan sangat mirip dengan yang saya tulis di atas sebagai s dan. Metode yang saya kodekan di atas berfungsi dengan baik untuk saya. Tapi saya hanya ingin tahu apakah ada algoritma standar untuk melakukan ini.   -  person Goku    schedule 21.02.2012

Jawaban (1)


arrow_upward
1
arrow_downward

Ini bukan pencocokan pola, ini adalah pengenalan pola, yang secara fundamental berbeda dan berpotensi jauh lebih sulit.

Namun, jenis pola sederhana yang ditunjukkan oleh string ini dapat ditemukan menggunakan (kode Python):

def find_repeated_pattern(s):
    for i in xrange(1, len(s) / 2):
        if s == s[:i] * (len(s) / i):
            return s[:i]

Ini adalah implementasi yang naif karena semua stringnya disalin, tetapi dapat dibuat berfungsi dalam waktu O(n²) dan ruang konstan.

person Fred Foo    schedule 20.02.2012
comment
Hai. Terima kasih untuk balasan Anda. Sebenarnya string di mana saya seharusnya menemukan polanya juga dihasilkan secara dinamis. Saya bukan ahli python tetapi apakah cuplikan kode ini akan berfungsi untuk string apa pun atau spesifik seperti kode yang saya tulis. - person Goku; 21.02.2012