[hiho 01]最长回文子串、Manacher算法
- 基础方法:枚举子串,判断是否为回文串。
- 改进:枚举中间位置,向两侧拓展。
- 再改进:利用以前的信息,使得不用每个新位置都从长度1开始拓展。
- 优化:将字符串预处理为奇数长度以避免考虑条件分支。
- 再优化:开头加入特殊字符避免考虑边界。
Manacher 算法:
id 是中心点,mx 是其边界。P[i] 表示以 i 为中心的最长回文子串的折半长度。
只要 i < mx, 以 i 为中心的回文子串就可以不必从长度1开始找,而从min{P[j], mx - i}开始(其中j为i关于id的对称点)。
当mx可以向右前进时(i + P[i] > mx),改变id和mx的值。
具体实现的代码如下:
#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; #define MAX_SIZE 1000000 char str[2 * MAX_SIZE + 10]; int p[2 * MAX_SIZE + 10]; int main() { int T; scanf("%d", &T); while (T--) { scanf("%s", str); int n = strlen(str); for (int i = n - 1; i >= 0; i--) { str[2*i+2] = str[i]; str[2*i+3] = ‘#‘; } str[0] = ‘$‘; str[1] = ‘#‘; memset(p, 0, sizeof(p)); int id = 0, mx = 0; int res = 0; for (int i = 1; i < 2*n+4; i++) { p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1; while (str[i + p[i]] == str[i - p[i]]) { p[i]++; } res = max(res, p[i]); if (i + p[i] > mx) { mx = i + p[i]; id = i; } } printf("%d\n", res - 1); } return 0; }
吐槽:p数组大小没乘2,但是hiho居然报wa。白找了半天错。
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。