strings/test/Enumerate_Palindromes.test.cpp

• View this file on GitHub
• Last update: 2023-07-25 00:50:50+07:00
• Problem: https://judge.yosupo.jp/problem/enumerate_palindromes

Depends on

• strings/manacher.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes"

#include <bits/extc++.h>

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

#include "../manacher.hpp"

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cin.exceptions(cin.failbit);
  string s;
  cin >> s;
  auto ans = manacher(s);
  for (auto v : ans) cout << v - 1 << ' ';
}

#line 1 "strings/test/Enumerate_Palindromes.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes"

#include <bits/extc++.h>

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

#line 1 "strings/manacher.hpp"
vector<int> manacher_odd(string s) {
  int n = s.size();
  s = "$" + s + "^";
  vector<int> p(n + 2);
  int l = 1, r = 1;
  for (int i = 1; i <= n; i++) {
    p[i] = max(0, min(r - i, p[l + (r - i)]));
    while (s[i - p[i]] == s[i + p[i]]) {
      p[i]++;
    }
    if (i + p[i] > r) {
      l = i - p[i], r = i + p[i];
    }
  }
  return vector<int>(begin(p) + 1, end(p) - 1);
}

vector<int> manacher(const string &s) {
  string t;
  for (auto c : s) {
    t += string("#") + c;
  }
  auto res = manacher_odd(t + "#");
  return vector<int>(begin(res) + 1, end(res) - 1);
}
#line 10 "strings/test/Enumerate_Palindromes.test.cpp"

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cin.exceptions(cin.failbit);
  string s;
  cin >> s;
  auto ans = manacher(s);
  for (auto v : ans) cout << v - 1 << ' ';
}

Back to top page