test/library_checker/string/enumerate_palindromes.test.cpp

• View this file on GitHub
• Last update: 2022-09-02 02:22:16+09:00
• Problem: https://judge.yosupo.jp/problem/enumerate_palindromes

Depends on

• 最長回文 (Manacher's Algorithm) (string/manacher.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes"
#include <bits/stdc++.h>
using namespace std;
#include "../../../string/manacher.hpp"
int main(){
  string S;
  cin >> S;
  int N = S.size();
  string T = "$";
  for (int i = 0; i < N; i++){
    T += S[i];
    T += '$';
  }
  vector<int> ans = manacher(T);
  for (int i = 1; i < N * 2; i++){
    cout << ans[i] - 1;
    if (i < N * 2 - 1){
      cout << ' ';
    }
  }
  cout << endl;
}

#line 1 "test/library_checker/string/enumerate_palindromes.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes"
#include <bits/stdc++.h>
using namespace std;
#line 2 "string/manacher.hpp"
template <typename T>
vector<int> manacher(const T &A){
  int N = A.size();
  vector<int> ans(N, 0);
  int i = 0, j = 0;
  while (i < N){
    while (i >= j && i + j < N && A[i - j] == A[i + j]){
      j++;
    }
    ans[i] = j;
    int k = 1;
    while (i >= k && i + k < N && k + ans[i - k] < j){
      ans[i + k] = ans[i - k];
      k++;
    }
    i += k;
    j -= k;
  }
  return ans;
}
#line 5 "test/library_checker/string/enumerate_palindromes.test.cpp"
int main(){
  string S;
  cin >> S;
  int N = S.size();
  string T = "$";
  for (int i = 0; i < N; i++){
    T += S[i];
    T += '$';
  }
  vector<int> ans = manacher(T);
  for (int i = 1; i < N * 2; i++){
    cout << ans[i] - 1;
    if (i < N * 2 - 1){
      cout << ' ';
    }
  }
  cout << endl;
}

Back to top page