【POJ2406】Power Strings（KMP，后缀数组）

 var a,x,y,sa,rank,height,dp,wc,wd:array[..]of longint;

     n,m,i,j,len,ans,st:longint;

     ch:ansistring;

     flag:boolean;

 function min(x,y:longint):longint;

 begin

  if x<y then exit(x);

  exit(y);

 end;

 function cmp(a,b,l:longint):boolean;

 begin

  exit((y[a]=y[b])and(y[a+l]=y[b+l]));

 end;

 procedure swap(var x,y:longint);

 var t:longint;

 begin

  t:=x; x:=y; y:=t;

 end;

 procedure getsa(n:longint);

 var i,j,p:longint;

 begin

  for i:= to m do wc[i]:=;

  for i:= to n- do

  begin

   x[i]:=a[i];

   inc(wc[a[i]]);

  end;

  for i:= to m- do wc[i]:=wc[i-]+wc[i];

  for i:=n- downto  do

  begin

   dec(wc[x[i]]);

   sa[wc[x[i]]]:=i;

  end;

  j:=; p:=;

  while p<n do

  begin

   p:=;

   for i:=n-j to n- do

   begin

    y[p]:=i; inc(p);

   end;

   for i:= to n- do

    if sa[i]>=j then begin y[p]:=sa[i]-j; inc(p); end;

   for i:= to n- do wd[i]:=x[y[i]];

   for i:= to m- do wc[i]:=;

   for i:= to n- do inc(wc[wd[i]]);

   for i:= to m- do wc[i]:=wc[i-]+wc[i];

   for i:=n- downto  do

   begin

    dec(wc[wd[i]]);

    sa[wc[wd[i]]]:=y[i];

   end;

   for i:= to n do swap(x[i],y[i]);

   p:=; x[sa[]]:=;

   for i:= to n- do

    if cmp(sa[i-],sa[i],j) then x[sa[i]]:=p-

     else begin x[sa[i]]:=p; inc(p); end;

   j:=j*;

   m:=p;

  end;

 end;

 procedure getheight(n:longint);

 var i,j,k:longint;

 begin

  for i:= to n do rank[sa[i]]:=i;

  k:=;

  for i:= to n- do

  begin

   if k> then dec(k);

   j:=sa[rank[i]-];

   while a[i+k]=a[j+k] do inc(k);

   height[rank[i]]:=k;

  end;

 end;

 {procedure init;

 begin

  fillchar(a,sizeof(a),0);

  fillchar(x,sizeof(x),0);

  fillchar(y,sizeof(y),0);

  fillchar(sa,sizeof(sa),0);

  fillchar(rank,sizeof(rank),0);

  fillchar(height,sizeof(height),0);

  fillchar(dp1,sizeof(dp1),0);

  fillchar(dp2,sizeof(dp2),0);

 end;     }

 begin

  assign(input,'data.in'); reset(input);

  assign(output,'poj2406.out'); rewrite(output);

  while not eof do

  begin

   //init;

   readln(ch);

   n:=length(ch);

   if ch='.' then break;

   for i:= to n do

   begin

    height[i]:=; sa[i]:=; rank[i]:=;

    dp[i]:=;

   end;

   for i:= to n- do a[i]:=ord(ch[i+]);

   a[n]:=; m:=;

   getsa(n+);

   getheight(n);

   dp[rank[]]:=maxlongint;

   for i:=rank[]+ to n do dp[i]:=min(height[i],dp[i-]);

   for i:=rank[]- downto  do dp[i]:=min(height[i+],dp[i+]);

   ans:=;

   for i:= to n div  do

    if n mod i= then

    begin

     st:=n-i;

     if dp[rank[i]]=n-i then begin ans:=n div i; break; end;

    end;

   writeln(ans);

  end;

 end.

 var a:ansistring;

     next:array[..]of longint;

     n,i,j:longint;

 begin

  while not eof do

  begin

   readln(a);

   if a='.' then break;

   n:=length(a);

   i:=; j:=;

   next[]:=;

   while j<=n do

   begin

    if (i=)or(a[i]=a[j]) then

    begin

     inc(i); inc(j);

     next[j]:=i;

    end

     else i:=next[i];

   end;

   if n mod (n-next[n+]+)= then

    writeln(n div (n-next[n+]+))

     else writeln();

   for i:= to n+ do next[i]:=;

  end;

 end.