poj2752 Seek the Name, Seek the Fame 2012-1-11

 1 Program Stone;
 2 var i,j,k,n:longint;
 3     b,a:array[1..400000]of longint;
 4     s:ansistring;
 5 Begin
 6  assign(input,‘input.in‘);reset(input);
 7    while not(eof) do
 8     begin
 9        readln(s);
10        j:=0;b[1]:=0;
11        for i:=2 to length(s) do
12         begin
13           while (j>0)and(s[i]<>s[j+1]) do j:=b[j];
14           if s[i]=s[j+1] then inc(j);
15           b[i]:=j;
16         end;
17        i:=length(S);
18        k:=0;
19        while i<>0 do
20         begin
21           inc(k);
22           a[k]:=i;
23           i:=b[i];
24         end;
25        for i:=k downto 1 do write(a[i],‘ ‘);
26        writeln;
27     end;
28   close(input);
29 end.