回文(manacher)

时间：2023-08-21 17:31:02

回文(manacher)

裸manacher

我竟然写跪了…………

一个地方（偶数）没写清楚……

我OOXOXOXOXXOXO

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<functional>

#include<cmath>

#include<cctype>

#include<cassert>

#include<climits>

using namespace std;

#define For(i,n) for(int i=1;i<=n;i++)

#define Rep(i,n) for(int i=0;i<n;i++)

#define Fork(i,k,n) for(int i=k;i<=n;i++)

#define ForD(i,n) for(int i=n;i;i--)

#define Forp(x) for(int p=pre[x];p;p=next[p])

#define RepD(i,n) for(int i=n;i>=0;i--)

#define MEM(a) memset(a,0,sizeof(a))

#define MEMI(a) memset(a,127,sizeof(a))

#define MEMi(a) memset(a,128,sizeof(a))

#define INF (2139062143)

#define F (1000000009)

#define MAXN (16777216+10)

typedef long long ll;

int n,r[MAXN],maxlen,maxbegin;

char s[MAXN];

int main()

{

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

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

   scanf("%s",s+1);n=strlen(s+1);

   int j=0;r[0]=0;

   For(i,n)

   {

      r[i]=1;

      if (j+r[j]>i) r[i]=min(r[j-(i-j)],j+r[j]-i);

      while (i-r[i]>=1&&i+r[i]<=n&&s[i-r[i]]==s[i+r[i]]) r[i]++;

      if (i+r[i]>j+r[j]) j=i;

   }

   maxlen=0;

   For(i,n) if (maxlen<r[i]*2-1) maxlen=r[i]*2-1,maxbegin=i-r[i]+1;

// cout<<maxlen<<' '<<maxbegin<<endl;

// For(i,n) cout<<r[i]<<' ';

   j=0;r[0]=0;memset(r,0,sizeof(r));

   For(i,n-1)

   {

      r[i]=0;

      if (j+r[j]>i) r[i]=min(r[j-(i-j-1)-1],j+r[j]-i);

      while (i+1-r[i]>1&&i+r[i]<n&&s[i-r[i]]==s[i+1+r[i]]) r[i]++;

      if (i+r[i]>j+r[j]) j=i;

   }

   For(i,n-1) if (maxlen<r[i]*2) maxlen=r[i]*2,maxbegin=i-r[i]+1;

   printf("%d\n",maxlen);

   Fork(i,maxbegin,maxbegin+maxlen-1) putchar(s[i]);puts("");

//   cout<<maxlen<<' '<<maxbegin<<endl;   

// while(1);

   return 0;

}

相关文章