链接：https://www.luogu.org/problemnew/show/P3805
思路：模板，直接上马拉车
代码：
1 //#include<bits/stdc++.h> 2 #include<iostream> 3 #include<vector> 4 #include<stack> 5 #include<string> 6 #include<cstdio> 7 #include<algorithm> 8 #include<queue> 9 #include<map> 10 #include<set> 11 #include<cmath> 12 #define inf 0x3f3f3f3f 13 using namespace std; 14 typedef long long ll; 15 const ll M = ll(1e7) * 3 + 5; 16 string s; 17 string s2; 18 ll len[M]; 19 string init(string s) 20 { 21 s2.clear(); 22 s2 += '@'; 23 for (ll i = 0; i < s.size(); i++) 24 { 25 s2 += '#'; 26 s2 += s[i]; 27 } 28 //s2 += s[s.size() - 1]; 29 s2 += '#'; 30 // s2 += '$'; 31 // s2 += ' '; 32 return s2; 33 } 34 ll Manacher(string s) 35 { 36 ll p0 = 0, mx = 0, ans = 0; 37 for (ll i = 1; i < s.size(); i++) 38 { 39 if (i < mx) 40 len[i] = min(mx - i, len[2 * p0 - i]); 41 else 42 len[i] = 1; 43 while (s[i - len[i]] == s[i + len[i]]) 44 len[i]++; 45 if (i + len[i] > mx) 46 { 47 mx = len[i] + i; 48 p0 = i; 49 } 50 ans = max(ans, len[i]); 51 } 52 return ans - 1; 53 } 54 int main() 55 { 56 while (cin >> s) 57 { 58 s = init(s); 59 //cout << s << endl; 60 cout << Manacher(s) << endl; 61 } 62 return 0; 63 }
备注：在初始化原串的时候要注意还需要再加一个不同的字符，我这里用的是@，防止马拉车的时候上溢，详情可见这篇博客