[POJ3974]Palindrome（后缀数组 || manacher）

传送门

求一个串的最长回文子串的长度

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] 软件补丁问题（状压最短路）

下一篇：后缀数组

---

后缀数组 Manacher