之前看过一次,但是现在又忘记了,觉得有必要自己写一篇笔记。
参考博客:https://blog.csdn.net/Charles_Zaqdt/article/details/79747073
网上有很多马拉车算法的详解,我就不赘述了。
- 首先对于长度为n的字符串s,要向其中插入n+1个该字符串中没有出现过的字符,比如#,这样新字符串news的长度就都是奇数了
- 下标从0开始
- len[i]表示news中以i为中心的最长回文子串长度的一半
- mx表示当前最长回文子串的下一位
- id表示当前最长回文子串的中心所在的位置
- 很重要的一点:当i>mx时,len[i]=min(mx-i,len[2*id-i),否则len[i]=1,然后再向两边扩展
- 当len[i]+i>mx时,更新mx、id和ans,注意:最终ans-1才是结果:例如对于news的一部分#a#b#a#,b的下标为i,那么len[i]=4,如果#a#b#a#就是news中的最长回文子串,那么原字符串s中的最长回文子串长度应该是len[i]-1=3,即aba的长度
裸题:
hihoCoder1032 (单纯的求最长回文子串,但是这道题如果字符串用string存的话会re??很迷,用char[]存才过(´・Д・)」)
ac代码:
#include <iostream>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <fstream>
const int maxn=3e6+10;
#define lowbit(x) (x&(-x))
typedef long long ll;
const ll mod=1e9+7;
using namespace std;
int leng,len[maxn],ans=0;
char s[maxn],news[maxn];
void init()
{
int k=0;
leng=strlen(s);
for(int i=0;i<leng;i++)
{
news[k++]='#';
news[k++]=s[i];
}
news[k++]='#';
leng=k;//实际长度,不是下标
}
int manacher()
{
memset(len,0,sizeof(len));
int id=0,mx=0;
for(int i=0;i<leng;i++)//从第一个#开始
{
if(i<mx) len[i]=min(mx-i,len[2*id-i]);
else len[i]=1;
while((i-len[i])>=0 && (i+len[i])<leng && news[i-len[i]]==news[i+len[i]]) len[i]++;
if(len[i]+i>mx)
{
mx=len[i]+i;
id=i;
ans=max(ans,len[i]);
}
}
return ans-1;
}
int main()
{
freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
int t;
cin>>t;
while(t--)
{
ans=0;
cin>>s;
init();
cout<<manacher()<<endl;
}
//string ss;
//cout<<"size: "<<ss.max_size()<<endl;
return 0;
}