内容目录
|
Power Strings
Description
给你一个字符串a，问a最多由几个完全相同的子串连接而成
Input
每一个测试点都会给你一个长度为m（1<=m<=1000000)的字符串，并以句号结尾。
Output
输出a最多由几个完全相同的子串连接而成。
Sample Input abcd aaaa ababab . Sample Output 1 4 3 Hint
用cin会T
Source |
这题要用到KMP算法中next的性质……我研究了一上午才搞懂
一个字母的next表示这个字母要向后跳到哪一位才能与原字符串匹配
a b c a b c
0 0 0 1 2 3
释义：第2个a=1->若不匹配可跳到第一个字符为起点（0表示完全不匹配）
经过观察发现
abcabcabc
000123456
a a i a a i a a i
0 10 1 2 3 4 5 6
于是发现next函数的嵌套关系：
L1-L2
L1-L2 L3-L4
于是如果一个字符串是循环的，那么最后的next正好就应该指向循环的那个圈
即便本身有自带的链也满足，观察下图即可当证明了：
Program PowerString;
const
maxn=10000010;
var
n,i,j,duan_luo:longint;
next:array[0..maxn] of longint;
a,b:ansistring;
function check:boolean;
var
i,j:longint;
begin
if (n mod duan_luo>0) then exit(false);
for i:=duan_luo+1 to n do if (a[i]<>a[i-duan_luo]) then exit(false);
exit(true);
end;
begin
while not eof do
begin
readln(a);
if a='.' then break;
n:=length(a);
j:=0; i:=1; next[1]:=0;
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]:=next[j]
else next[i]:=j;
end
else j:=next[j];
end;
duan_luo:=n-next[i];
if check then writeln(n div duan_luo) else writeln(1);
end;
end.
代码2（前面的next总觉得有问题，于是我自行修改）：
Program PowerString;
const
maxn=10000010;
var
n,i,j,duan_luo:longint;
next:array[0..maxn] of longint;
a,b:ansistring;
function check:boolean;
var
i,j:longint;
begin
if (n mod duan_luo>0) then exit(false);
for i:=duan_luo+1 to n do if (a[i]<>a[i-duan_luo]) then exit(false);
exit(true);
end;
begin
while not eof do
begin
readln(a);
if a='.' then break;
n:=length(a);
j:=0; i:=1; next[1]:=0;
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]:=next[j]
while (j>0) and (a[i]<>a[j]) do j:=next[j];
next[i]:=j;
end
else j:=next[j];
end;
duan_luo:=n-next[i];
if check then writeln(n div duan_luo) else writeln(1);
end;
end.
代码3：（最后那个if好像就用不着了……）：
Program PowerString;
const
maxn=10000010;
var
n,i,j,duan_luo:longint;
next:array[0..maxn] of longint;
a,b:ansistring;
function check:boolean;
var
i,j:longint;
begin
if (n mod duan_luo>0) then exit(false);
for i:=duan_luo+1 to n do if (a[i]<>a[i-duan_luo]) then exit(false);
exit(true);
end;
begin
while not eof do
begin
readln(a);
if a='.' then break;
n:=length(a);
j:=0; i:=1; next[1]:=0;
while (i<n) do
begin
inc(i);inc(j);
//if (a[i]<>a[j]) then next[i]:=next[j]
while (j>0) and (a[i]<>a[j]) do j:=next[j];
next[i]:=j;
end;
duan_luo:=n-next[i];
if check then writeln(n div duan_luo) else writeln(1);
end;
end.
代码4：这层while有有只递增i，感觉没必要：
Program PowerString;
const
maxn=10000010;
var
n,i,j,duan_luo:longint;
next:array[0..maxn] of longint;
a,b:ansistring;
function check:boolean;
var
i,j:longint;
begin
if (n mod duan_luo>0) then exit(false);
for i:=duan_luo+1 to n do if (a[i]<>a[i-duan_luo]) then exit(false);
exit(true);
end;
begin
while not eof do
begin
readln(a);
if a='.' then break;
n:=length(a);
j:=0; i:=1; next[1]:=0;
for i:=2 to n do
begin
inc(j);
//if (a[i]<>a[j]) then next[i]:=next[j]
while (j>0) and (a[i]<>a[j]) do j:=next[j];
next[i]:=j;
end;
duan_luo:=n-next[i];
if check then writeln(n div duan_luo) else writeln(1);
end;
end.