Manacher
朴素算法
vector<int> d1(n);
for (int i = 0; i < n; i++) {
d1[i] = 1;
while (0 <= i - d1[i] && i + d1[i] < n && s[i - d1[i]] == s[i + d1[i]]) {
d1[i]++;
}
}
Manacher 算法
过程
Manacher 算法的实现
vector<int> d1(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
k++;
}
d1[i] = k--;
if (i + k > r) {
l = i - k;
r = i + k;
}
}
统一处理
以上方案仅考虑了回文串长度为奇数时的情况,但实际上可以通过一个技巧将偶数长度也归纳进来。
int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) k++;
对于该处理过程,以下结论不难证明:
模板
https://www.luogu.com.cn/problem/P3805
//#define LOCAL
#include<bits/stdc++.h>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
#define print(x) cout<<(x)<<'\n'
#define forn(i, n) for(long long i=0; i<n; i++)
#define sum(a) ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a) (*min_element((a).begin(), (a).end()))
#define maxe(a) (*max_element((a).begin(), (a).end()))
#define mini(a) ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a) ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-4;
const double PI = acos(-1);
const int MAXN = 1e5 + 29;
struct point {
int left, right, w;
} tree[MAXN];
int n;
int fa[MAXN];
string s, str;
int d1[(int) 1.1e7 * 2 + 10];
void manacher(int odd_length = str.size()) {
for (int i = 1, l = 0, r = -1; i < odd_length; i++) {
int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
while (0 <= i - k && i + k < odd_length && str[i - k] == str[i + k]) {
k++;
}
d1[i] = k--;
if (i + k > r) {
l = i - k;
r = i + k;
}
}
}
signed main() {
#ifdef LOCAL
freopen("output.txt", "w", stdout);
freopen("input.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
getline(cin, s);
str.push_back(7);
for (const auto &item: s) {
str.push_back(6);
str.push_back(item);
}
str.push_back(6);
manacher();
print(*max_element(d1, d1 + str.size()) - 1);
}
Reference
最后更新于