[CF30E]Tricky and Clever Password(KMP+manacher)

首先枚举回文中心，然后显然中心两边要尽量扩展作为middle，这个用manacher实现。

然后注意到suffix的结尾位置是固定的（串尾），那么预处理出以每个位置结尾的串与原串后缀至多能匹配多长，然后再作个前缀和在枚举回文中心时尝试更新答案即可。这一部分将原串反过来用KMP实现，注意|suffix|可能为0。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 typedef long long ll;

 using namespace std;

 const int N=;

 char s[N],ss[N];

 int n,ans,pos,mx,id,nxt[N],r[N],f[N],g[N];

 int main(){

     freopen("e.in","r",stdin);

     freopen("e.out","w",stdout);

     scanf("%s",s+); n=strlen(s+); s[n+]='#';

     rep(i,,n){

         r[i]=(mx>i) ? min(r[*id-i],mx-i) : ;

         while (s[i+r[i]]==s[i-r[i]]) r[i]++;

         if (r[i]+i>mx) mx=r[i]+i,id=i;

     }

     rep(i,,n) ss[i]=s[n+-i];

     nxt[]=nxt[]=;

     for (int i=,j=; i<=n; i++){

         while (j && ss[j+]!=ss[i]) j=nxt[j];

         if (ss[j+]==ss[i]) nxt[i]=++j;

     }

     for (int i=,j=; i<=n; i++){

         while (j && ss[j+]!=s[i]) j=nxt[j];

         if (ss[j+]==s[i]) f[i]=++j;

         if (f[i]==n) j=nxt[j];

         if (f[i]) g[i]=i-f[i]+;

     }

     rep(i,,n) if (f[i-]>f[i]) f[i]=f[i-],g[i]=g[i-];

     bool flag=;

     rep(i,,n) if (*r[i]->ans) ans=*r[i]-,pos=i-r[i]+;

     rep(i,,n){

         int t=i-r[i];

         if (*min(f[t],n-(i+r[i]-))+*r[i]->ans) flag=,ans=*min(f[t],n-(i+r[i]-))+*r[i]-,pos=i;

     }

     if (!flag) printf("1\n%d %d\n",pos,ans);

         else printf("3\n%d %d\n%d %d\n%d %d\n",g[pos-r[pos]],f[pos-r[pos]],pos-r[pos]+,*r[pos]-,n-f[pos-r[pos]]+,f[pos-r[pos]]);

     return ;

 }