Алгоритм Манакера: различия между версиями

Текущая версия от 16:20, 20 декабря 2022

vector<int> oddPalindromeCount(string &s) {
    vector<int> palindromeCount(s.size(), 1);
    int l, r = -1;

    for (int i = 0; i < s.size(); i++) {
        int &p = palindromeCount[i];
        if (i <= r)
            p = min(palindromeCount[l + r - i], r - i);

        while (0 <= i - p && i + p < s.size() && s[i - p] == s[i + p])
            p++;

        if (i + p - 1 > r) {
            l = i - p + 1;
            r = i + p - 1;
        }
    }

    return palindromeCount;
}

vector<vector<int>> manacher(string &s) {
    string t = "#";
    for (char c : s) {
        t += c;
        t += '#';
    }

    vector<int> palindromeCount = oddPalindromeCount(t);

    vector<vector<int>> res(2);
    for (int i = 0; i + 1 < palindromeCount.size(); i++)
        res[i % 2].push_back(palindromeCount[i] / 2);
    return res;
}

vector<int> evenPalindromeCount(string &s) {
    vector<int> palindromeCount(s.size());
    int l, r = -1;

    for (int i = 0; i < s.size(); i++) {
        int &p = palindromeCount[i];
        if (i <= r)
            p = min(palindromeCount[l + r - i + 1], r - i + 1);

        while (0 <= i - p - 1 && i + p < s.size() && s[i - p - 1] == s[i + p])
            p++;

        if (i + p - 1 > r) {
            l = i - p;
            r = i + p - 1;
        }
    }

    return palindromeCount;
}

Ссылки

Теория:

Код:

Задачи:

Задачи: Алгоритм Манакера

@@ Строка 59: / Строка 59: @@
   }
 |}
+== Ссылки ==
+Теория:
+* [http://e-maxx.ru/algo/palindromes_count e-maxx.ru — Нахождение всех подпалиндромов за O(N)]
+* [https://cp-algorithms.com/string/manacher.html cp-algorithms.com — Manacher's Algorithm]
+* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9C%D0%B0%D0%BD%D0%B0%D0%BA%D0%B5%D1%80%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Манакера]
+* [https://algorithmica.org/ru/palindromes algorithmica.org — Палиндромы]
+* [https://usaco.guide/adv/string-search?lang=cpp#manacher usaco.guide — Manacher]
+Код:
+* [https://github.com/indy256/codelibrary/blob/master/cpp/strings/manacher.cpp indy256/codelibrary/cpp/strings/manacher.cpp]
+* [https://github.com/ADJA/algos/blob/master/Strings/ManacherPalindromes.cpp ADJA/algos/Strings/ManacherPalindromes.cpp]
+Задачи:
+* [[:Категория: Задачи: Алгоритм Манакера|Задачи: Алгоритм Манакера]]
+[[Категория:Строки]]

Алгоритм Манакера: различия между версиями

Текущая версия от 16:20, 20 декабря 2022

Ссылки

Навигация

Поиск