Question

北京大学acm题库2406题的解答

附上程序
Power Strings
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 4590 Accepted: 1859

Description
Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).

Input
Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

Output
For each s you should print the largest n such that s = a^n for some string a.

Sample Input

abcd
aaaa
ababab
.

Sample Output

1
4
3

Hint
This problem has huge input, use scanf instead of cin to avoid time limit exceed.

Source
Waterloo local 2002.07.01

Answer 1

program ddd;
var i,j,m,n,q,p,num:longint;
ps:array[0..1000000]of char;
pai:array[0..1000000]of longint;
procedure init;
var i,j:longint;
b:boolean;
function pd(l:longint):boolean;
var i:longint;
begin
if m mod l<>0 then exit(false);
for i:=2 to (m div l) do
if (pai[i*l]=0) or (pai[i*l] mod l<>0) then exit(false);
pd:=true;
end;
begin
m:=0;
while not eoln(input) do
begin
inc(m);
read(ps[m]);
end;
readln;
if (m=1) and (ps[1]='.') then halt;
if m=0 then begin writeln(0); exit end;
pai[1]:=0;
q:=0;
for i:=2 to m do begin
while (q>0) and (ps[q+1]<>ps[i]) do
q:=pai[q];
if ps[q+1]=ps[i] then inc(q);
pai[i]:=q;
end;
q:=0;
i:=1;
b:=true;
repeat
while (i<=m) and (pai[i]<>1) do inc(i);
dec(i);
if pd(i) then begin
writeln(m div i);
b:=false;
break;
end else begin
q:=i;
inc(i,2);
end;
until i>=m;
if b then writeln(1);
end;
begin
while true do init;
end.
（已ac）