Prefiks funksiyasi. Knut-Morris-Pratt algoritmi
Uzunligi bo‘lgan satr berilgan.
satrining pozitsiyasi uchun prefiks-funksiya — bu ostsatrining eng katta o‘z prefiksining uzunligi bo‘lib, u bir vaqtning o‘zida uning suffiksi ham bo‘ladi.
(O‘z prefiks — butun satrga teng bo‘lmagan prefiks.)
Formal ravishda:
Kelishuv bo‘yicha:
Misol:
Har qanday uchun:
Agar:
bo‘lsa, u holda:
Aks holda qisqaroq prefiksni izlash kerak.
Quyidagini olaylik:
Unda quyidagiga o‘tamiz:
va quyidagigacha yana tekshiramiz:
Agar moslik topilsa:
Aks holda:
satrining uning suffiksi bo‘ladigan maksimal o‘z prefiksi ga teng (agar ).
uchun:
Asimptotika:
vector<int> prefix_function(const string& s) {
int n = s.size();
vector<int> pi(n);
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && s[i] != s[j]) {
j = pi[j - 1];
}
if (s[i] == s[j]) {
j++;
}
pi[i] = j;
}
return pi;
}