网站建设网页开发,怎么学视频剪辑制作,网站建设销售培训,广东专业的网站制作马拉车算法 Manacher‘s Algorithm 是用来查找一个字符串的最长回文子串的线性方法#xff0c;由一个叫
Manacher 的人在 1975 年发明的#xff0c;这个方法的最大贡献是在于将时间复杂度提升到了线性
dp[i] ma i ? min(dp[2 * mod - i], ma - i) : 1;
可以这么说由一个叫
Manacher 的人在 1975 年发明的这个方法的最大贡献是在于将时间复杂度提升到了线性
dp[i] ma i ? min(dp[2 * mod - i], ma - i) : 1;
可以这么说这行要是理解了那么马拉车算法基本上就没啥问题了那么这一行代码拆开来看就是
如果 ma i, 则 p[i] min( dp[2 *mod - i] , ma - i )
否则dp[i] 1本身)
【care一】mai
1当 ma - i dP[j] 的时候以S[j]为中心的回文子串包含在以 S[mod] 为中心的回文子串中由于 i 和 j 对称以 S[i] 为中心的
回文子串必然包含在以 S[mod] 为中心的回文子串中所以必有 P[i] P[j]其中 j 2*id - i因为 j 到 id 之间到距离等于
id 到 i 之间到距离为 i - id所以 j id - (i - id) 2*id - i参见下图。ma的对称点 2*mod-i(i关于mod的对称点) (mod为能延伸到最右端的位置的那个回文子串的中心点位置)mi j mod i ma(记录向右边延伸最多的位置)
—————|—————————|———————————————|———————————————|—————————|——|————————|————————————— ———————|—————————|| dp[j] |(以dp[j]表示以v[j]字符为中心的回文子串的半径)—————————————————————————————————————————————————————————————2当 dP[j] ma - i 的时候以 S[j] 为中心的回文子串不一定完全包含于以 S[mod] 为中心的回文子串中但是基于对称性可知
下图中两个绿框所包围的部分是相同的也就是说以 S[i] 为中心的回文子串其向右至少会扩张到 ma的位置也就是说 dP[i] ma - i。
至于 ma 之后的部分是否对称就只能老老实实去匹配了这就是后面紧跟到 while 循环的作用。ma的对称点 2*mod-i(i关于mod的对称点) (mod为能延伸到最右端的位置的那个回文子串的中心点位置)mi j mod i ma(记录向右边延伸最多的位置)
—————|—————————|———————————————|———————————————|———————————|————————||——————————|—————————| |——————————|———————————|——|| dp[j] | |(以dp[j]表示以v[j]字符为中心的回文子串的半径)|—————————————————————————————————————————————————————|【care二】
对于 ma i 的情况无法对 P[i] 做更多的假设只能 P[i] 1然后再去匹配了。
题目
给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度. 回文就是正反读都是一样的字符串,如aba, abba等
Input
输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S 两组case之间由空行隔开(该空行不用处理) 字符串长度len 110000
Output
每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.
Sample Input
aaaaabab
Sample Output
4
3
AC代码
#includestdio.h
#includestring.h
#includealgorithm
using namespace std;
const int M110010;
int dp[M*2];//dp[i]表示以v[i]字符为中心的回文子串的半径
char u[M],s[M*2];
int ans,len;
void manacher()
{/**马拉车算法的第一步是预处理做法是在每一个字符的左右都加上一个特殊字符比如加上 #这样做的好处是不论原字符串是奇数还是偶数个处理之后得到的字符串的个数都是奇数个*/int l0;s[l]$; //s[0]*,s[len*22]\0,防止在while时dp[i]越界s[l]#;//Manacher处理回文串时需要在每个字符串的中间以及两端插入不会出现的字符然后再枚举for(int i0; ilen; i) //插入了len1个#,最终的s长度是1~(lenlen1)即2*len1,首尾s[0]和s[2*len2]要插入不同的字符{s[l]u[i];s[l]#;}s[l]\0;int ma0,mod0;///ma记录向右边延伸最多的位置,for(int i0; il; i){dp[i]mai?min(dp[mod*2-i],ma-i):1;/**i为我们设定的回文串中心若ma则此时没有回文串被包含只能慢慢枚举其他详细分析见上*/while(s[dp[i]i]s[i-dp[i]]) dp[i];if(idp[i]ma){maidp[i];modi;}}
}
int main()
{while(~scanf(%s,u)){lenstrlen(u);manacher();ans-1;for(int i0; i2*len2; i)ansmax(ans,dp[i]-1);printf(%d\n,ans);}return 0;
}
