UVa/11512.pas

   1 const
   2   maxn=1100;
   3
   4 var
   5   tcase,m,n,i,k:longint;
   6   s,st:ansistring;
   7   sa,tsa,rk,trk,sum,h:array [0..maxn] of longint;
   8
   9 procedure suffix_array(var s:ansistring);
  10 var
  11   i,j,p:longint;
  12
  13 begin
  14   fillchar(sum,sizeof(sum),0);
  15   for i:=1 to n do
  16     begin
  17       trk[i]:=ord(s[i]);
  18       inc(sum[trk[i]]);
  19     end;
  20   for i:=1 to 255 do inc(sum[i],sum[i-1]);
  21   for i:=n downto 1 do
  22     begin
  23       sa[sum[trk[i]]]:=i;
  24       dec(sum[trk[i]]);
  25     end;
  26   rk[sa[1]]:=1;
  27   p:=1;
  28   for i:=2 to n do
  29     begin
  30       if trk[sa[i]]<>trk[sa[i-1]] then inc(p);
  31       rk[sa[i]]:=p;
  32     end;
  33   j:=1;
  34   while j<n do
  35     begin
  36       move(rk,trk,sizeof(rk));
  37       fillchar(sum,sizeof(sum),0);
  38       p:=0;
  39       for i:=n-j+1 to n do
  40         begin
  41           inc(p);
  42           tsa[p]:=i;
  43         end;
  44       for i:=1 to n do
  45         if sa[i]>j then
  46           begin
  47             inc(p);
  48             tsa[p]:=sa[i]-j;
  49           end;
  50       for i:=1 to n do
  51         begin
  52           rk[i]:=trk[tsa[i]];
  53           inc(sum[rk[i]]);
  54         end;
  55       for i:=1 to n do inc(sum[i],sum[i-1]);
  56       for i:=n downto 1 do
  57         begin
  58           sa[sum[rk[i]]]:=tsa[i];
  59           dec(sum[rk[i]]);
  60         end;
  61       rk[sa[1]]:=1;
  62       p:=1;
  63       for i:=2 to n do
  64         begin
  65           if (trk[sa[i]]<>trk[sa[i-1]]) or (trk[sa[i]+j]<>trk[sa[i-1]+j]) then inc(p);
  66           rk[sa[i]]:=p;
  67         end;
  68       j:=j shl 1;
  69     end;
  70   h[1]:=0;
  71   p:=0;
  72   for i:=1 to n do
  73     begin
  74       if rk[i]=1 then continue;
  75       j:=sa[rk[i]-1];
  76       while s[i+p]=s[j+p] do inc(p);
  77       h[rk[i]]:=p;
  78       if p>0 then dec(p);
  79     end;
  80 end;
  81
  82 function kmp(var p,t:ansistring):longint;
  83 var
  84   i,j:longint;
  85   next:array [0..maxn] of longint;
  86
  87 begin
  88   m:=length(p);
  89   j:=0;
  90   next[1]:=0;
  91   for i:=2 to m do
  92     begin
  93       while (j>0) and (p[j+1]<>p[i]) do j:=next[j];
  94       if p[j+1]=p[i] then inc(j);
  95       next[i]:=j;
  96     end;
  97   j:=0;
  98   kmp:=0;
  99   for i:=1 to n do
 100     begin
 101       while (j>0) and (p[j+1]<>t[i]) do j:=next[j];
 102       if p[j+1]=t[i] then inc(j);
 103       if j=m then
 104         begin
 105           inc(kmp);
 106           j:=next[j];
 107         end;
 108     end;
 109 end;
 110
 111 begin
 112   readln(tcase);
 113   repeat
 114     dec(tcase);
 115     readln(s);
 116     s:=s+'$';
 117     n:=length(s);
 118     suffix_array(s);
 119     k:=1;
 120     for i:=2 to n do if h[i]>h[k] then k:=i;
 121     st:=copy(s,sa[k],h[k]);
 122     if st='' then writeln('No repetitions found!') else
 123       writeln(st,' ',kmp(st,s));
 124   until tcase=0;
 125 end.