POJ 1961(KMP前缀最长重复子串）

Posted on by
内容目录
Language:
Period
Time Limit: 3000MS   Memory Limit: 30000K
Total Submissions: 10179   Accepted: 4662

Description

求一个字符串中，所有循环节大于2的子串。

Input

有若干组数据，
每组数据第一行为字符串长度，第二行为字符串
以0结束。

Output

对于每组数据，输出'Test case #i",i从0开始，之后每行输出两个数，分别表示前缀长度和循环节数（>1).
每组数据后输出一个空行。

Sample Input

3
aaa
12
aabaabaabaab
0

Sample Output

Test case #1
2 2
3 3

Test case #2
2 2
6 2
9 3
12 4

Source

Southeastern Europe 2004

这题就是KMP问题。

还是Next，

先做不判重复优化的处理

观察发现若前面有循环节，则有i->i-p->i-2p...->i-kp=1

则i-next[i]表示循环结长度p，显然有p|（i-1),(i-1) div p>1.

如下:



Program Poj1961;
const
   maxn=10000000;
var
   i,j,tt,n,duan_luo:longint;
   next:array[1..maxn] of longint;
   a:ansistring;
begin
   tt:=1;
   while (true) do
   begin
      readln(n);
      if n=0 then break;
      readln(a);  inc(n); a:=a+'.';
      i:=1;j:=0;next[1]:=0;
      while (i<=n-1) 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;

      writeln('Test case #',tt);

      for i:=2 to n do
      begin
         duan_luo:=i-next[i];
         if (duan_luo>0) and ((i-1) mod duan_luo=0) and ((i-1) div duan_luo>1) then
            writeln(i-1,' ',(i-1) div duan_luo);



      end;

//    readln;
      writeln;
      inc(tt);
   end;

end.