传送门
求一个串的最长回文子串的长度
1.后缀数组
把这个串反转后接到原串的后面，中间连一个没有出现过的字符。
然后求这个新字符串的某两个后缀的公共前缀的最大值即可。
——代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define N 2000010 5 #define max(x, y) ((x) > (y) ? (x) : (y)) 6 7 int n, m, len, ans; 8 int buc[N], x[N], y[N], sa[N], rank[N], height[N]; 9 char s[N]; 10 11 inline void build_sa() 12 34 } 35 36 inline void build_height() 37 48 } 49 50 int main() 51 70 return 0; 71 }View Code
2.manacher
#include <cstdio> #include <cstring> #define N 2100000 #define min(x, y) ((x) < (y) ? (x) : (y)) #define max(x, y) ((x) > (y) ? (x) : (y)) int p[N]; char s[N]; int n, pos, maxright, ans; int main() ans = max(ans, p[i] 1); } printf("Case %d: %d\n", cnt, ans); } return 0; }
上一篇：[luoguP2761] 软件补丁问题（状压最短路）
下一篇：[POJ3294]Life Forms（后缀数组）
后缀数组 Manacher
