首页 > 代码库 > manacher hihoCoder1032 最长回文子串
manacher hihoCoder1032 最长回文子串
居然能够做到O(n)的复杂度求最长回文。,也是给跪了。
以下这个人把manacher讲的很好,,能够看看
http://blog.csdn.net/xingyeyongheng/article/details/9310555
我就照着他的代码敲了一遍贴了个模板。。
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<string> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #include<functional> using namespace std; const int MX = 1e6 + 5; char s[MX * 2];//记得要开两倍 int p[MX * 2]; int manacher(char *s){ int len = strlen(s), id = 0, ans = 0; for(int i = len; i >= 0; i--) { s[i + i + 2] = s[i]; s[i + i + 1] = ‘#‘; } s[0] = ‘*‘;//防越界,非常重要!! for(int i = 2; i < 2 * len + 1; ++i) { if(p[id] + id > i) p[i] = min(p[2 * id - i], p[id] + id - i); else p[i] = 1; while(s[i - p[i]] == s[i + p[i]]) p[i]++; if(id + p[id] < i + p[i]) id = i; ans = max(ans, p[i] - 1); } return ans; } int main() { int T; scanf("%d", &T); while(T--) { scanf("%s", s); printf("%d\n", manacher(s)); } return 0; }
manacher hihoCoder1032 最长回文子串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。