题目链接
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 inline ll read(){
5 int x = 0, f = 1; char ch = getchar();
6 while(ch > '9' || ch < '0'){if (ch == '-') f = -1; ch = getchar();}
7 while(ch >= '0' && ch <= '9'){ x = x*10+ch-'0'; ch = getchar();}
8 return x*f;
9 }
10
11 /************************************************************************/
12
13 const int maxn = 1e6+7;
14 char s[maxn];
15 char str[maxn];
16 int dp1[maxn], p[maxn];
17 int dp2[maxn];
18 int len;
19
20 void manacher(char s[], int len){
21 int ans = 0;
22 for(int i = 1;i <= len;i++){
23 str[i<<1] = s[i];
24 str[(i<<1)+1] = '#';
25 }
26 str[1] = '#'; str[len*2+1] = '#';
27 str[0] = '&'; str[len*2+2] = '$';
28 len = len*2+1;
29 int j = 0, k;
30 for(int i = 1;i <= len;){
31 while(str[i-j-1] == str[i+j+1]) j++;
32 p[i] = j;
33 if(j > ans) ans = j;
34 for(k = 1;k <= j && (p[i]-k != p[i-k]);k++){
35 p[i+k] = min(p[i-k], p[i] - k);
36 }
37 i += k;
38 j = max(j-k, 0);
39 }
40 }
41
42 int main(){
43 scanf("%s", s+1);
44 len = strlen(s+1);
45 manacher(s, len);
46 len = len*2+1;
47 cout << "str: " << str << endl;
48 for(int i = 1;i <= len;i++){
49 for(int j = p[i];j >= 1;j--){
50 if(dp1[i+j] >= j) break;
51 dp1[i+j] = j;
52 }
53 for(int j = p[i];j >= 1;j--){
54 if(dp2[i-j] >= j) break;
55 dp2[i-j] = j;
56 }
57 }
58 int ans = 0;
59 for(int i = 1;i <= len-2;i++){
60 if(dp1[i] && dp2[i])
61 ans = max(ans, dp1[i] + dp2[i]);
62 }
63 cout << ans << endl;
64 return 0;
65 }