AcWing 回文子串的最大长度
Description
如果一个字符串正着读和倒着读是一样的，则称它是回文的。
给定一个长度为N的字符串S，求他的最长回文子串的长度是多少。
Input
输入将包含最多30个测试用例，每个测试用例占一行，以最多1000000个小写字符的形式给出。
输入以一个以字符串“END”（不包括引号）开头的行表示输入终止。
Output
对于输入中的每个测试用例，输出测试用例编号和最大回文子串的长度（参考样例格式）。
每个输出占一行。
Sample Input
abcbabcbabcbaabacacbaaaabEND
Sample Output
Case 1: 13Case 2: 6
题解：
- 字符串哈希。
- “正着读反着读都一样“… …那正着推一遍哈希值，逆着推一遍哈希值，然后直接比较哈希值是否相等就行了。
- 复杂度大概是O(n ^ 2)，如果用尺取的思想可以降到O(n)，但是我蒻没想到尺取思想。所以写了二分。
- 我们知道回文串有奇数回文串和偶数回文串。那么我们对这两种类型的回文串分别做二分，过程中取最大长度就好了。复杂度为O(nlogn)
- 顺带一提，马拉车算法可以O(n)解决此题。
#include#include #include #define N 1000005#define int unsigned long longusing namespace std;string t;int tim, len;int p[N], f1[N], f2[N];bool check(int val){ int l1, r1, l2, r2; for(l1 = 1; l1 <= len; l1++) { r1 = l1 + val / 2; if(val % 2 == 0) l2 = r1, r1--; else l2 = r1 + 1, r1--; r2 = l1 + val - 1; if(r1 > len || r2 > len) break; if(f1[r1] - f1[l1 - 1] * p[r1 - l1 + 1] == f2[l2] - f2[r2 + 1] * p[r2 - l2 + 1]) return 1; } return 0;}signed main(){ while(cin >> t) { if(t == "END") break; len = t.size(); p[0] = 1; for(int i = 1; i <= len; i++) p[i] = p[i - 1] * 131; for(int i = 0; i < len; i++) f1[i + 1] = f1[i] * 131 + (t[i] - 'a' + 1); f2[len + 1] = 0; for(int i = len; i >= 1; i--) f2[i] = f2[i + 1] * 131 + (t[i - 1] - 'a' + 1); //细节：因为把int换成了ull，所有i不能为负 int l = 0, r = len + 1, ans = 0; while(l <= r) { int mid = (l + r) >> 1; if(mid % 2 == 0) mid++; if(check(mid)) l = mid + 2, ans = max(ans, mid); else r = mid - 2; } l = 0, r = len + 1; while(l <= r) { int mid = (l + r) >> 1; if(mid % 2) mid++; if(check(mid)) l = mid + 2, ans = max(ans, mid); else r = mid - 2; } printf("Case %lld: %lld\n", ++tim, ans); } return 0;}