Bu sorunu çözmek için olağan numaralandırma çalışmaz, çünkü asimptotikleri
O(t*s) olacaktır. Bu nedenle, alt dizi arama görevleri için KMP (Knuth-Morris-Pratt) algoritması kullanılır.
Bu algoritmayı uygulamak için, dize ön eki işlevi kullanılır; bu,
n (strong>s uzunluk) uzunluğundaki sayılardan oluşan bir dizidir; buradaki her öğe, maksimum uzunluktur
s alt dizesinin en büyük kendi son ekinin ön ekiyle eşleşir. Örneğin:
| Çizgi |
Önek işlevi |
Not |
| abababcab |
0 0 1 2 3 4 0 1 2 |
|
| abcabcd |
0 0 0 1 2 3 0 |
|
| aabaaab |
0 1 0 1 2 2 3 |
|
O(n^3) asimptotikli önemsiz önek işlev algoritması:
vektör<int> önek_işlevi (dize s) {
int n = (int ) s.uzunluk();
vektör<int>pi(n);
için (int i=0; i<n; ++i)
için (int k=0; k<=i; ++k)
if (s.substr(0,k) == s .substr(i-k+1,k))
pi[i] = k;
dönüşpi;
}
Ve şimdi şu şekilde bir dizi için bir önek işlevi yapmamız gerekiyor: & nbsp; t + # + s; burada #, metinde olmadığı açıkça görülen bir sınırlayıcı karakterdir. Önek işlevinin karşılık gelen ayırıcı karakterden sonraki değerlerini inceleyerek, elde edilen değerin istenen alt dizenin uzunluğuna eşit olması durumunda oluşumunun bulunduğuna dikkat edilmelidir. Örneğin, "abababcab" ve istenen "abab" alt dizesi, önek işlevi şöyle olacaktır:
0 0 1 2 0 1 2 3 4 3 4 0 1 2 karşılık gelen dizgenin öğelerini ayrıştırmamız gerekiyor s:
1 2 3 4 3 4 0 1 2 - Değerin 4 olduğu iki durum vardır (4. ve 6.), yani. uzunluk t, sonuç olarak cevap yazılmalıdır: 4 - 4 (uzunluk t) & nbsp; = 0 ve 6 - 4 = 2. Bunların doğru cevaplar olduğu ve "abab" aslında "abababcab" 0 ve 2 konumlarında.
Önek işlevini optimize ettikten sonra (ayrıntılar için burada ), O(n) asimptotikli son algoritmayı elde ederiz:
vektör<int> önek_işlevi (dize s) {
int n = (int ) s.uzunluk();
vektör<int>pi(n);
for (int i=1; i<n; ++i) {
int j = pi[i-1< /span>];
while (j > 0 && s[i] != s[j])
j = pi[j-1];
if (s[i] == s[j]) ++j;
pi[i] = j;
}
dönüşpi;
}
|
Z-fonksiyonu
S dizisinden Z-fonksiyonu - her elemanı Z olan Z dizisi [i ], S dizgisinde i konumundan başlayan alt dizgenin en uzun önekine eşittir, bu aynı zamanda tüm Z. Sıfır konumundaki Z-fonksiyonunun değeri genellikle sıfırdır veya tüm dizenin uzunluğudur.
Zorluk
O(|S| ^ 2) veya O(|S|).
S - P dizisinden önek işlevi, her elemanı P[i] dizinin en uzun sonekine eşittir. S dizgisindeki < code>i konumundan başlayan bir alt dizgi; bu aynı zamanda S dizgisinin tamamının soneki. Sıfır konumundaki P-fonksiyonunun değeri genellikle sıfırdır veya tüm dizenin uzunluğudur.
Zorluk
O(|S| ^ 2) veya O(|S|).
O(|S| ^ 2) için Z işlevini ve önek işlevini uygulamaya çalışın .
|
O(|S|) içindeki bir dizide bir alt dizi bulmak için KMP(Knuth-Morris-Pratt) algoritmasını uygulamak için hem Z hem de işlev öneki kullanılabilir. Bu algoritmanın özü şu şekildedir: Aradığımız diziyi bulmak istediğimiz diziye atfederiz. Bu satırların arasına bir ayırıcı karakter, yani herhangi bir satırda geçmeyen bir karakter (genellikle #) koymak çok arzu edilir.
|