pku1961 Period

求一个字符串中每一个前缀用s’^k(k>1)表示的所有情况。要求输出该前缀的结束位置和k值。

和2406有基本相同的方法，求出next数组后枚举i，看(1-i) mod(i-next[i])是否大于1，满足条件就输出即可。

View Code

 1 program pku1961(input,output);
 2 var
 3    n     : longint;
 4    ch     : char;
 5    s     : ansistring;
 6    next     : array[0..1000100] of longint;
 7    i,j     : longint;
 8    cases : longint;
 9 begin
10    readln(n);
11    cases:=0;
12    while n<>0 do
13    begin
14       inc(cases);
15       s:='';
16       for i:=1 to n do
17       begin
18      read(ch);
19      s:=s+ch;
20       end;
21       readln;
22       fillchar(next,sizeof(next),0);
23       j:=0;
24       next[1]:=0;
25       for i:=2 to length(s) do
26       begin
27      while (j>0)and(s[i]<>s[j+1]) do
28         j:=next[j];
29      if s[i]=s[j+1] then
30         inc(j);
31      next[i]:=j;
32       end;
33       writeln('Test case #',cases);
34       for i:=2 to length(s) do
35      if ((i mod (i-next[i]))=0)and((i div (i-next[i]))>1) then
36         writeln(i,' ',i div (i-next[i]));
37       writeln;
38       readln(n);
39    end;
40 end.