求連續重復次數最多的子串（字典序最小）
首先連續出現一次一定是可行的，我們考慮出現兩次及以上
我們考慮窮舉這個子串長度l，如果某個這個長度的子串出現了兩次以上
那他一定包含包含某兩個字符s[l*m+1],s[l*(m+1)+1]
這樣，我們先判斷每對字符能延伸多長（先求LCP，然后判斷是否能再向前延伸）
poj1741，窮舉長度L 的時間是n，每次計算的時間是n/L。所以整個做法的時間復雜度是O(n/1+n/2+n/3+……+n/n)=O(nlogn)
1 var h,ans,y,x,sum,rank,sa:array[0..100010] of longint; 2 f:array[0..100010,0..20] of longint; 3 d:array[0..20] of longint; 4 b,e,p,te,i,j,max,t,l,n,m:longint; 5 s:ansistring; 6 7 function cmp(a,b,j:longint):boolean; //注意這里排序判斷要這么寫（因為多測） 8 begin 9 if y[a]<>y[b] then exit(true); 10 if (a+j<=n) and (b+j<=n) and (y[a+j]<>y[b+j]) then exit(true); 11 if (a+j<=n) and (b+j<=n) then exit(false) 12 else exit(true); 13 end; 14 15 procedure swap(var a,b:longint); 16 var c:longint; 17 begin 18 c:=a; 19 a:=b; 20 b:=c; 21 end; 22 23 function min(a,b:longint):longint; 24 begin 25 if a>b then exit(b) else exit(a); 26 end; 27 28 procedure suffix; 29 var i,j,p,m:longint; 30 begin 31 fillchar(sum,sizeof(sum),0); 32 m:=255; 33 for i:=1 to n do 34 begin 35 y[i]:=ord(s[i]); 36 inc(sum[y[i]]); 37 end; 38 for i:=2 to m do 39 inc(sum[i],sum[i-1]); 40 for i:=n downto 1 do 41 begin 42 sa[sum[y[i]]]:=i; 43 dec(sum[y[i]]); 44 end; 45 p:=1; 46 rank[sa[1]]:=1; 47 for i:=2 to n do 48 begin 49 if y[sa[i]]<>y[sa[i-1]] then inc(p); 50 rank[sa[i]]:=p; 51 end; 52 m:=p; 53 j:=1; 54 while m<n do 55 begin 56 fillchar(sum,sizeof(sum),0); 57 y:=rank; 58 p:=0; 59 for i:=n-j+1 to n do 60 begin 61 inc(p); 62 x[p]:=i; 63 end; 64 for i:=1 to n do 65 if sa[i]>j then 66 begin 67 inc(p); 68 x[p]:=sa[i]-j; 69 end; 70 71 for i:=1 to n do 72 begin 73 rank[i]:=y[x[i]]; 74 inc(sum[rank[i]]); 75 end; 76 for i:=1 to m do 77 inc(sum[i],sum[i-1]); 78 for i:=n downto 1 do 79 begin 80 sa[sum[rank[i]]]:=x[i]; 81 dec(sum[rank[i]]); 82 end; 83 p:=1; 84 rank[sa[1]]:=1; 85 for i:=2 to n do 86 begin 87 if cmp(sa[i],sa[i-1],j) then inc(p); 88 rank[sa[i]]:=p; 89 end; 90 m:=p; 91 j:=j shl 1; 92 end; 93 p:=0; 94 for i:=1 to n do 95 begin 96 if rank[i]=1 then continue; 97 j:=sa[rank[i]-1]; 98 while (i+p<=n) and (j+p<=n) and (s[i+p]=s[j+p]) do inc(p); 99 h[rank[i]]:=p; 100 if p>0 then dec(p); 101 end; 102 end; 103 104 procedure rmq; 105 var i,j,t:longint; 106 begin 107 t:=trunc(ln(n)/ln(2)); 108 d[0]:=1; 109 for i:=1 to t do 110 d[i]:=d[i-1]*2; 111 for i:=1 to n do 112 f[i,0]:=h[i]; 113 for j:=1 to t do 114 for i:=1 to n do 115 if i+d[j]-1<=n then 116 f[i,j]:=min(f[i,j-1],f[i+d[j-1],j-1]) 117 else break; 118 end; 119 120 function ask(x,y:longint):longint; 121 var k:longint; 122 begin 123 if x>y then swap(x,y); 124 inc(x); 125 k:=trunc(ln(y-x+1)/ln(2)); 126 exit(min(f[x,k],f[y-d[k]+1,k])); 127 end; 128 129 begin 130 while true do 131 begin 132 inc(te); 133 readln(s); 134 if s='#' then break; 135 n:=length(s); 136 suffix; 137 rmq; 138 max:=1; 139 ans[1]:=0; 140 t:=1; 141 for l:=1 to n do 142 begin 143 i:=1; 144 while i+l<=n do 145 begin 146 p:=ask(rank[i],rank[i+l]); 147 m:=p div l+1; 148 j:=i-(l-p mod l); //判斷是否能再向前延伸 149 if (j>0) and (p mod l<>0) then 150 begin 151 if ask(rank[j],rank[j+l])>=p then 152 inc(m); 153 end; 154 if m>max then 155 begin 156 max:=m; 157 t:=1; 158 ans[1]:=l; 159 end 160 else if (m=max) and (ans[t]<>l) then 161 begin 162 inc(t); 163 ans[t]:=l; 164 end; 165 i:=i+l; 166 end; 167 end; 168 b:=0; e:=0; 169 for i:=1 to n do 170 begin 171 for j:=1 to t do 172 if (sa[i]+ans[j]<=n) and (sa[i]+max*ans[j]-1<=n) and (ask(i,rank[sa[i]+ans[j]])>=(max-1)*ans[j]) then 173 begin 174 b:=sa[i]; 175 e:=b+max*ans[j]-1; 176 break; 177 end; 178 179 if b<>0 then break; 180 end; 181 write('Case ',te,': '); 182 for i:=b to e do 183 write(s[i]); 184 writeln; 185 end; 186 end.
?
