POJ 2752(不满足P[i]<>P[next[i]] 的next函数）

Posted on by
内容目录
Language:
Seek the Name, Seek the Fame
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 8682   Accepted: 4112

Description

给定一个字符串P，求它所有的满足P[1..i]到P[n-i+1..n]的i.

Input

数据有若干行
每行为一组数据P,1 <= Length of P <= 400000. 

Output

每行一组数据，按数字升序输出所有的i. 

Sample Input

ababcababababcabab
aaaaa

Sample Output

2 4 9 18
1 2 3 4 5

Source

POJ Monthly--2006.01.22,Zeyuan Zhu


要考虑KMP中Next函数的性质-P[next[i]]<>P[i]

如果这个条件不满足呢？

先在字符串后插入一个'.'，表示'.'前的循环，这样就能规避这一点（因为‘.’不会与任何字母重合）

再把后面那个if从句删掉(它只能跳过一些-非全部的-P[next[i]]<>P[i]的情况，因为.后面可能出现两次'a'

这样就可以了，最后把答案（由于不考虑a[i],只考虑前面循环节的长度，故-1）


Program SeekName;
const
    maxn=400000;
var
   n,i,j,size:longint;
   a:ansistring;
   ans,next:array[1..maxn] of longint;

begin
   while not seekeof do
   begin
      readln(a); a:=a+'.';
      n:=length(a);
      j:=0;next[1]:=0;i:=1;
      while (i<n) do
      begin
         if (j=0) or (a[i]=a[j]) then
         begin
            inc(i);
            inc(j);
         //   if (a[i]<>a[j]) then next[i]:=j else next[i]:=next[j];
            next[i]:=j;
         end else j:=next[j];
      end;
      size:=0; j:=n;
      repeat
         inc(size);
         ans[size]:=j-1;
         j:=next[j];
      until j<=1;


      write(ans[size]);
      for i:=size-1 downto 1 do write(' ',ans[i]);
      writeln;



   end;

end.