Module: Önek işlevi, Z işlevi

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:
 

O(n^3) asimptotikli önemsiz önek işlev algoritması:


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.

 

Ç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

#	Girdi	Çıktı
1	abababcab abab	0 2

Write the program below
#include <iostream> #include <vector> #include <string> using namespace std; vector<int> prefix_function(string s) { int n = (int)s.length(); vector<int> pi(n); for (int i = 0; i < n; ++i) for (int k = 0; k <= i; ++k) if (s.substr(0, k) == s.substr(i - k + 1, k)) pi[i] = k; return pi; } int main() { string s, t; cin >> s >> t; s = t + '#' + s; vector<int> pi; pi = prefix_function(s);
return 0; }