有一个长度不超过400000的字符串s，求满足{既是s的前缀，又是s的后缀}的字串，输出每一个串的起始位置。
首先，它本身满足条件，接下来，用KMP求出next数组，每次去掉next[i]到i的一段字符，剩余字串仍满足条件，直到找到头为止。
View Code 1 program pku2752(input,output); 2 var 3 s : ansistring; 4 next : array[0..500000] of longint; 5 answer : array[0..500000] of longint; 6 total : longint; 7 i,j : longint; 8 begin 9 while not eof do 10 begin 11 readln(s); 12 fillchar(next,sizeof(next),0); 13 j:=0; 14 next[1]:=0; 15 for i:=2 to length(s) do 16 begin 17 while (s[i]<>s[j+1])and(j>0) do 18 j:=next[j]; 19 if s[i]=s[j+1] then 20 inc(j); 21 next[i]:=j; 22 end; 23 total:=0; 24 i:=length(s); 25 while i<>0 do 26 begin 27 inc(total); 28 answer[total]:=i; 29 i:=next[i]; 30 end; 31 for i:=total downto 1 do 32 write(answer[i],' '); 33 writeln; 34 end; 35 end.