Функсияи префиксӣ. Алгоритми Кнут-Моррис-Пратт
Сатри бо дарозии дода шудааст.
Функсияи префикс -и сатри барои мавқеи — ин дарозии бузургтарин префикси хоси зерсатри мебошад, ки ҳамзамон суффикси он низ ҳаст.
(Префикси хос — ба тамоми сатр баробар нест.)
Расман:
Тибқи созиш:
Мисол:
Барои ҳар гуна :
Агар:
пас:
Дар акси ҳол бояд префикси кӯтоҳтарро ҷуст.
Бигузор:
Он гоҳ мегузарем ба:
ва боз месанҷем, то даме ки:
Агар мувофиқат ёфт шавад:
Дар акси ҳол:
Бузургтарин префикси хоси сатри , ки суффикси он мебошад, ба баробар аст (агар ).
Барои :
Асимптотика:
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;
}