之前看过一次,但是现在又忘记了,觉得有必要自己写一篇笔记。

参考博客: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;
}