Строковые алгоритмы: Префикс-функция (КМП), Z-функция и Бойер-Мур

1. Префикс-функция и Алгоритм Кнута-Морриса-Пратта (КМП)

Префикс-функция $\pi[i]$ — длина наибольшего собственного префикса подстроки $S[0..i]$ , который одновременно является её суффиксом.

cpp

vector<int> prefixFunction(const string& s) {
    int n = s.length();
    vector<int> pi(n, 0);
    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;
}

2. Z-функция (Фундаментальная предварительная обработка)

$Z[i]$ — длина наибольшего общего префикса строки $S$ и её суффикса, начинающегося с позиции $i$ :

Z[i] = \max \{ k \mid S[0..k-1] = S[i..i+k-1] \}

Алгоритм поддерживает отрезок $[L, R]$ с максимальным $R$ и работает за строгое $O(N)$ время.

cpp

vector<int> zFunction(const string& s) {
    int n = s.length();
    vector<int> z(n, 0);
    int l = 0, r = 0;
    for (int i = 1; i < n; ++i) {
        if (i <= r) z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

3. Алгоритм Бойера-Мура

Алгоритм сопоставляет шаблон справа налево, используя 2 эвристики сдвига:

Правило плохого символа (Bad Character Rule): сдвигает шаблон до последнего вхождения несовпавшего символа текста;

Правило хорошего суффикса (Good Suffix Rule): сдвигает шаблон так, чтобы совпавший суффикс совместился с другим вхождением в шаблоне (вычисляется через таблицы

L', l', N

В лучшем случае время работы составляет $O(N / M)$ (сублинейное!).

Строковые алгоритмы: Префикс-функция (КМП), Z-функция и Бойер-Мур

1. Префикс-функция и Алгоритм Кнута-Морриса-Пратта (КМП)

2. Z-функция (Фундаментальная предварительная обработка)

3. Алгоритм Бойера-Мура

Что дальше?