// Manacher算法，很好用。 char s[2*N]; //储存临时串int save[2*N];//中间记录int Manacher(char tmp[]){    int len=strlen(tmp);    int cnt=0;    for(int i=0;i
     
      =p)        {            int num=1;            while(i+num
      
       =0&&s[i+num]==s[i-num])            {                num++;            }            p=i+num-1; //能到达的最远位置            a=i;            save[i]=num-1; //从这个位置出发最长的回文            if(save[i]==0) continue;            if(s[i]=='#')            {                if(2*((save[i]-1)/2 +1)>mx) mx=2*((save[i]-1)/2+1);            }            else            {                if(2*(save[i]/2)+1>mx) mx=2*(save[i]/2)+1;            }        }        else        {            int j=2*a-i;            if( i+save[j] < p)            {                save[i]=save[j];                if(save[i]==0) continue;                if(s[i]=='#')                {                    if(2*((save[i]-1)/2 +1)>mx) mx=2*((save[i]-1)/2+1);                }                else                {                    if(2*(save[i]/2)+1>mx) mx=2*(save[i]/2)+1;                }            }            else            {                int k=2*i-p;                while(p+1
       
        =0&&s[p+1]==s[k-1])                {                    p++;                    k--;                }                a=i;                save[i]=p-i;                if(save[i]==0) continue;                if(s[i]=='#')                {                    if(2*((save[i]-1)/2 +1)>mx) mx=2*((save[i]-1)/2+1);                }                else                {                    if(2*(save[i]/2)+1>mx) mx=2*(save[i]/2)+1;                }            }        }    }    return mx;}
       
      
     

 

kmp，扩展kmp

// 感觉kmp可以理解。 #define N 100010int s[N];int next[N];int t[N];int main(){    //freopen("//home//chen//Desktop//ACM//in.text","r",stdin);    //freopen("//home//chen//Desktop//ACM//out.text","w",stdout);    int T;    scanf("%d",&T);    while(T--)    {        int n,m;        scanf("%d%d",&n,&m);        for(int i=0;i

 

最小表示法

int mistr(char s[],int len)  //输入一串字符，返回最小表示法的起始位置{    int i=0,j=1,k=0;    while(i
     
      
       
         s[j+k]) i=i+k+1;            if(s[i+k] < s[j+k]) j=j+k+1;            k=0;            if(i==j) j++;        }    }    return min(i,j);}