学步园

先上 超时 直接 用C++ 的string  居然会超时 。。。最后换成了 char 才可以。。。

#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
using namespace std ;
const int maxn = 220010 ;
int p[maxn] ;
void insert(string &ins , string &outs)
{
	outs[0] = '$' ;
	string :: iterator iter = ins.begin();
	int len = 1 ;
	while( iter != ins.end())
	{
		 outs[len++] = '#' ;
		 outs[len++] = *iter ;
		 iter++ ;
	}
/*	for ( int i = 0 ; i < ins.size();++i)
	{
		 outs[len++] = '#' ;
		 outs[len++] = ins[i] ;
		 
	}
*/
	     outs[len] = '#' ;
	 
}

void manacher(string &outs)
{
	int mx = 0 , id = 0 ;
	memset(p, 0, sizeof(p));
	for( int i = 0 ; i < outs.size() ;++i)
	{
		 p[i] = mx > i ? min(p[2*id-i],mx -i) : 1;
		 while(outs[i+p[i]] == outs[i-p[i]])  p[i]++ ;
		 if( i + p[i] > mx )
		 {
		 	  mx =  i + p[i] ;
		 	  id = i ;
		 }
	}
}

int main()
{
	string s ;
   while(cin >> s) 
   {
	string res (2*s.size()+2 ,'a') ;
	insert(s,res) ;
	manacher(res);
    int length = 1 ;
    for ( int i = 0 ; i < res.size();++i)
              length = max(length,p[i]);
    printf("%d\n", length-1);
   }
	return 0 ;
	      
}

下面是为超时的 ，弄了一下午 才明白 为啥是这样的 。。。时间啊

#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std ;
const int MAXN=110005;
char sin[MAXN];
char sout[2*MAXN];
int p[2*MAXN];

int insert( char ins[] , char outs[])
{
	outs[0] = '$' ;
	int len = 1 ;
	int i = 0 ;
	while(  ins[i] != '\0')
	{
		 outs[len++] = '#' ;
		 outs[len++] = ins[i] ;
		 ++i;
	}
	outs[len++]='#';
    outs[len]=0;
    return len;
}

void manacher( char outs[] , int len)
{
	int mx = 0 , id = 0 ;
	memset(p, 0, sizeof(p));
	for( int i = 0 ; i < len ;++i)
	{
		 p[i] = mx > i ? min(p[2*id-i],mx -i) : 1;
		 while(outs[i+p[i]] == outs[i-p[i]])  p[i]++ ;
		 if( i + p[i] > mx )
		 {
		 	  mx =  i + p[i] ;
		 	  id = i ;
		 }
	}
}
int main()
{
	  while(scanf("%s",sin)!=EOF)
    {
        int len = insert(sin,sout);
        manacher(sout,len);
        int maxl=1;
        for(int i=0;i<len;i++)
             maxl=max(maxl,p[i]);
        printf("%d\n",maxl-1);
    }
    return 0;
}