一、算法原理
Manacher算法在对求字符串中最长回文串问题中,具有O(n)时间和空间复杂度。算法的精妙之处在于巧妙的利用了回文串的对偶性质。
第一步:对字符间添加间隔符,(例如,字符串aababcdab,通过添加间隔符转化为 #a#a#b#a#b#c#d#a#b#)从而避免了字符串的奇偶性问题,为了避免算法中考虑边界问题,可以在字符串首尾加入奇异符号(例如,$#a#a#b#a#b#c#d#a#b#&,因为C/C++字符串中有结束符\0,所以可可以省略尾端加入的奇异符);
第二步:更新模式数组p[],这里也是Manacher算法的核心所在,我当初看这块时纠结了好长时间。首先通过图片来说明一下:
假设当前处理位置在i点,且 i < mx(mx为关于坐标k对称子串的右边界为),即P[k] = mx - k。此时忽略左边界mx’又 i 关于 k 对称的坐标为 j ,这时就可以分成两种情况:
- P[j] > mx - i + 1 时,P[i] = mx - i + 1;因为 mx 和 mx’ ,i 和 j 为关于k对称,所以 S[ mx’, ~ ,j ] = S[ i, ~ ,mx ]。如果 P[i] > mx - i + 1,也即 S[mx+1] = S[2*i - mx - 1],而已知:S[mx’ -1] = S[2*j - mx’ + 1 ],j + i= 2*k,mx’ + mx= 2*k ,所以有S[mx’-1] = S[mx+1],这时以k为中心对称子串右边界变为了mx+1,矛盾。
- P[j] == mx - i + 1 时,P[i] >= P[j];证明方法和上面一样。
-
P[j] <”mx - i + 1 时,P[i] = P[j];证明方法和上面一样。
对于其他情况就需要重新匹配了。
第三步:找到(也可以在更新P[]时记录最大数)模式数组P[]中最大数减一,即为字符串中最大回文串长度。
二、程序
#include <iostream>
#include <string>
using namespace std;
int LongestPalindromicSubstring(const string& S, int& maxPos)
{
int *p = new int[S.size() + ];
memset(p, , sizeof(p));
int mx = , k = ;
int maxLength = ;
bool reCompute = false;
for(int i = ; i < S.size(); i++)
{
if( mx > i ) {
p[i] = (p[*k - i] < (mx - i) ? p[*k - i] : (mx - i + ));
reCompute = p[*k - i] == (mx - i + ) ? true : false;
}
else {
p[i] = ;
reCompute = true;
}
if( reCompute )
{
for(; S[ i+p[i] ] == S[i - p[i] ]; ++p[i]);
}
if( p[i] > maxLength)
{
maxPos = i;
maxLength = p[i];
}
if(i + p[i] > mx)
{
mx = i + p[i] - ;
k = i;
}
cout << S[i] << " ";
reCompute = false;
}
cout << endl;
for(int i = ; i < S.size(); i++)
{
cout << p[i] << " ";
}
cout << endl;
maxPos = maxPos/ - - --maxLength/;
delete p;
return maxLength;
}
int main()
{
string S = "aabababab";
string S_Process;
S_Process += "$#";
for(int i = ; i < S.size(); i++)
{
S_Process += S[i];
S_Process += "#";
}
cout << S_Process << endl;
int pos = ;
int length = LongestPalindromicSubstring(S_Process, pos);
cout << "max Longest Palindromic Substring is : " << S.substr(pos, length) << endl;
cout << "max length : " << length << endl;
return ;
}
结果: