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

Текущая версия от 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;
}

Ссылки

Теория:

Код:

Задачи:

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

@@ Строка 1: / Строка 1: @@
-  char s[1000010];
+{| width="100%"
- int n, odd[1000010], even[1000010];
+| width=50% |
+  vector<int> oddPalindromeCount(string &s) {
+     vector<int> palindromeCount(s.size(){{Changed|1=, 1}});
+     int l, r = -1;
- void oddPalindromesCount() {
+      for (int i = 0; i < s.size(); i++) {
-     int l = 0, r = -1;
+          int &p = palindromeCount[i];
-      for (int i = 0; i < n; i++) {
+         if (i <= r)
-          int k = (i > r ? 1 : min(odd[l + r - i], r - i));
+             p = min(palindromeCount[l + r - i], r - i);
-          while (i - k >= 0 && i + k < n && s[i - k] == s[i + k])
-              k++;
+          while (0 <= i - p && i + p < s.size() && s[i - p] == s[i + p])
-         odd[i] = k;
+              p++;
-          if (i + k - 1 > r) {
-              l = i - k + 1;
+          if (i + p - 1 > r) {
-              r = i + k - 1;
+              l = i - p {{Changed|1=+ 1}};
+              r = i + p - 1;
           }
       }
+     return palindromeCount;
   }
+ vector<vector<int>> manacher(string &s) {
+     string t = "#";
+     for (char c : s) {
+         t += c;
+         t += '#';
+     }
-  void evenPalindromesCount() {
+     vector<int> palindromeCount = oddPalindromeCount(t);
-      int l = 0, r = -1;
-      for (int i = 0; i < n; i++) {
+     vector<vector<int>> res(2);
-          int k = (i > r ? 0 : min(even[l + r - i - 1], r - i));
+     for (int i = 0; i + 1 < palindromeCount.size(); i++)
-          while (i - k >= 0 && i + k + 1 < n && s[i - k] == s[i + k + 1])
+         res[i % 2].push_back(palindromeCount[i] / 2);
-              k++;
+     return res;
-         even[i] = k;
+ }
-          if (i + k > r) {
+| width="10px" | &nbsp;
-              l = i - k + 1;
+| width=50% |
-              r = i + k;
+ 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 {{Changed|1=+ 1}}], r - i {{Changed|1=+ 1}});
+          while (0 <= i - p {{Changed|1=- 1}} && i + p < s.size() && s[i - p {{Changed|1=- 1}}] == s[i + p])
+              p++;
+          if (i + p - 1 > r) {
+              l = i - p;
+              r = i + p - 1;
           }
       }
+     return palindromeCount;
   }
+|}
 == Ссылки ==
 Теория:
-* [http://e-maxx.ru/algo/palindromes_count e-maxx.ru &mdash; Нахождение всех подпалиндромов за O(N)]
+* [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]
 Код:
-* [http://github.com/ADJA/algos/blob/master/Strings/ManacherPalindromes.cpp Algos &mdash; Manacher's algorithm]
+* [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

Ссылки

Навигация

Поиск