#include <stdio.h>
#include <string.h>
#include <ctype.h>

char s[400001];
int n;

int next[40001];
int nrec;
int rec[40001];

main() {
	int x; char ch;
	
//	freopen( "e.in", "r", stdin );
//	freopen( "e.out", "w", stdout );
	
	while( (ch = getchar()) != EOF ) {
		if( !islower(ch) ) break;
		n = 0;
		do {
			s[n++] = ch;
			ch = getchar();
		} while( islower(ch) );
		x = 0;
		for( int i = 1; i < n; i++ ) {
			while( x && s[i] != s[x] ) x = next[x];
			if( s[i] == s[x] ) x++;
			next[i] = x;
		}
		nrec = 0;
		for( x = n-1; x >= 0; x = next[x]-1 ) rec[nrec++] = x;
		for( int i = nrec-1; i >= 0; i-- ) printf( "%d ", rec[i]+1 );
		printf( "\n" );
	}
}

• ms...next和rec数组开小了 (0) sayforever 2006-01-23 01:29:35
  • 改大了还是TLE.. (0) Maximum 2006-01-23 19:55:59
    • KMP写的有问题。。。 照你那样写的话，会出现（x == next[x] && x > 0)的情况 (0) sayforever 2006-01-23 22:00:44
      • Re:KMP写的有问题。。。 照你那样写的话，会出现（x == next[x] && x > 0)的情况 (24) yuehufengyi 2014-02-14 13:27:02
        • Re:KMP写的有问题。。。 照你那样写的话，会出现（x == next[x] && x > 0)的情况 (21) yuehufengyi 2014-02-14 13:50:38
• Re:请教一下，偶的程序哪里写错了，总是TLE (768) hzoizjz 2014-07-31 07:12:36
• Re:请教一下，偶的程序哪里写错了，总是TLE (19) hzoizjz 2014-07-31 07:13:25