POJ 2406(KMP中next的性质）
Power StringsTime Limit: 3000MS Memory Limit: 65536KTotal Submissions: 24403 Accepted: 10264

Description

给你一个字符串a，问a最多由几个完全相同的子串连接而成

Input

每一个测试点都会给你一个长度为m（1<=m<=1000000)的字符串，并以句号结尾。

Output

输出a最多由几个完全相同的子串连接而成。

Sample Input

abcdaaaaababab.

Sample Output

143

Hint

用cin会T

Source

Waterloo local 2002.07.01

这题要用到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;      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.