2752.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2752  User Id:fzk 
#include "stdio.h"
#include "string.h"
#include "memory.h"
char w1[410000];
char w2[410000];
bool ok[410000];
int next1[410000];
int next2[410000];

void get_next(int *next,char *w,int len)
{
   int i=1,j=0;
   next[1]=0;
   while(i<=len)
   {
      if(j==0||w[i]==w[j])
      {
         i++;j++;
         //if(w[i]!=w[j])
            next[i]=j;
         //else next[i]=next[j];
      }
      else j=next[j];
   }
   return;
}

int main( ) {
	int i, j, len;
	while( scanf( "%s", w1+1 ) == 1 ) {
		len = strlen( w1+1 );
		for( i=0; i<len; i++ )
			w2[i+1] = w1[ len-i];
		w2[len+1] = '\0';

		get_next( next1, w1, len );
		get_next( next2, w2, len );
		memset( ok, 0, sizeof ok );
		
		for( i=len+1, j=len+1; i>1 && j>1; ) {
			if( i == j )
				ok[ i-1 ] = true;
			
			if( next1[i] >= next2[j] )
				i = next1[i];
			else
				j = next2[j];
		}

		for( i=1; i<len; i++ )
			if( ok[i] )
				printf( "%d ", i );
		printf( "%d\n", len );
	}

	return 0;
}