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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: « char s[1000010]; int n, odd[1000010], even[1000010]; void oddPalindromesCount() { int l = 0, r = -1; for (int i = 0; i < n; i++) { int k =…»)
 
Нет описания правки
Строка 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://github.com/ADJA/algos/blob/master/Strings/ManacherPalindromes.cpp Algos &mdash; Manacher's algorithm]
Задачи:
* [[:Категория: Задачи: Алгоритм Манакера|Задачи: Алгоритм Манакера]]
 
[[Категория:Строки]]

Версия от 16:12, 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;
}