This documentation is automatically generated by competitive-verifier/competitive-verifier
連続部分文字列の最長回文の半径を求める.
文字列 S
の連続部分文字列のそれぞれの中心について,最長の回文の半径を格納する配列 v
を返す.
manacher(S)
:i
文字目を中心とする最長の回文の半径を v[i]
に格納する.manacher_even(S)
:i
文字目を中心とする最長の回文の半径を v[2*i]
に,i
文字目と i+1
文字目の境を中心とする最長の回文の半径を v[2*i+1]
に格納する.#pragma once
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
vector<int> manacher(const string &S) {
int N = S.length();
vector<int> res(N, 1);
for(int i = 0, c = 0; i < N; i++) {
int l = c - (i - c);
if(i + res[l] < c + res[c]) {
res[i] = res[l];
}
else {
int r = c + res[c] - i;
while(i - r >= 0 && i + r < N && S[i - r] == S[i + r]) r++;
res[i] = r;
c = i;
}
}
return res;
}
vector<int> manacher_even(const string &S) {
string S2;
for(const char &c : S) (S2 += c) += '$';
S2.pop_back();
vector<int> res = manacher(S2);
for(int i = 0; i < S.length() - 1; i++) {
++res[i + i] >>= 1;
res[i + i + 1] >>= 1;
}
++res[res.size() - 1] >>= 1;
return res;
}
#line 2 "string/manacher.cpp"
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
vector<int> manacher(const string &S) {
int N = S.length();
vector<int> res(N, 1);
for(int i = 0, c = 0; i < N; i++) {
int l = c - (i - c);
if(i + res[l] < c + res[c]) {
res[i] = res[l];
}
else {
int r = c + res[c] - i;
while(i - r >= 0 && i + r < N && S[i - r] == S[i + r]) r++;
res[i] = r;
c = i;
}
}
return res;
}
vector<int> manacher_even(const string &S) {
string S2;
for(const char &c : S) (S2 += c) += '$';
S2.pop_back();
vector<int> res = manacher(S2);
for(int i = 0; i < S.length() - 1; i++) {
++res[i + i] >>= 1;
res[i + i + 1] >>= 1;
}
++res[res.size() - 1] >>= 1;
return res;
}