算法介绍
算法原理
对于一个字符串要判断它是否为回文串要分为字符串长度为奇数或者偶数两种情况，为了简化做法，我们进行如下的操作:
- 在字符串的两端和每两个字符中间添加一个 ‘#’ (或者任意一个一定不会在字符串中出现的字符, 通常就是 ‘#’ 啦)
- 再在字符串的开始和结尾放置字符串开始和结束的标识符。
上述操作后拓展出来的字符串的长度一定是奇数。
例如:
abcd 拓展后变为 ^#a#b#c#d#$ abc 拓展后变为 ^#a#b#c#$ 这里举个例子 s[] = "abac" str[] ^ # a # b # a # c # $ dp[] 1 2 1 4 1 2 1 2 1 int right; // 在计算过程中用于记录寻找到所有子回文串中右边界的下标 int pos; // 用于记录右边界就是right的子回文串的下标 ---------------------------------------------------- ^ ^ ^ |<--------------------|-------------------->| left pos right 如果 i 在 pos 和 right 之间，则可以寻找 i 关于 pos 的对称点，这时可以先假设dp[i] = dp[2*pos-i]，这个假设并不在任何情况下都成立:
如果中心为 2*pos-i 的回文串覆盖的区域左边界超过了left，则这个回文串中存在一些可能不在中心为 i 的回文串中的元素，这种情况下dp[i] = right-i
将上述讨论的情况结合起来即可得到:
dp[i] = min(dp[2*pos-i], right-i)
如果 i > right 那我们就用暴力的方法求解dp[i]即可
算法实现
int Manacher(char* s) {
int len = strlen(s+1); char str[2*len+10]; int dp[2*len+10]; int cur = 0; str[0] = '^'; for(int i = 0; i < len; ++i) {
str[++cur] = '#'; str[++cur] = s[i]; } str[++cur] = '#', str[++cur] = '$'; int right = 0, pos = 0; for(int i = 1; i <= cur; ++i) {
if(i < right) dp[i] = min(dp[2*pos-i], right-i); else dp[right=i] = 1; while(str[i-dp[i]] == str[i+dp[i]]) ++dp[i]; if(i+dp[i] > right) right = i+dp[i], pos = i; } return *max_element(dp+1, dp+cur+1)-1; } 特别感谢
感谢我女朋友对我的大力支持?。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/233984.html原文链接：https://javaforall.net
