Default Milking Grid Description (1 <= R <= 10,000) *C (1 <= C <= 75) 的矩阵，求它的最大平铺矩阵,不够的地方可部分平铺，但不可重叠。 Input 第一行：R和C. 第2-R+1行每行C个大写字母，表示矩阵. Output 最大的平铺矩阵面积 Sample Input 2 5ABABAABABA Sample Output 2 Hint The entire milking grid can be constructed from repetitions of the pattern 'AB'. Source |
Time Limit: 3000MS | | Memory Limit: 65536K |
Total Submissions: 4346 | | Accepted: 1780 |
显然这个矩阵必然从左上角开始
由于C比较少，先找出每列最大的平铺线段（行行不影响）
再考虑每行共有且最小的重复部分（可以证明增加重复部分对行的大小无影响）
在考虑行R≤10000，必须用Kmp，不凡假设句末有若干'????'
则对于字符串的P
AEICCCAEICCCAEI C C ? ? ? ...
000000123456789 10 11 12 13 14 ...
显然？后的P递增+1，又因答案为Max（i-p[i])（i≥n）
所以(n-p[n])=Max（i-p[i])
Program grid;
const
maxn=10000;
maxm=75;
var
n,m,i,j,k:longint;
a:array[1..maxn] of string;
f:array[1..maxm] of longint;
flag:boolean;
p:array[1..maxn] of longint;
begin
fillchar(f,sizeof(f),0);
readln(n,m);
for i:=1 to n do
begin
readln(a[i]);
for j:=1 to m do
begin
flag:=true;
for k:=j+1 to m do
if a[i][k]<>a[i][k-j] then begin flag:=false; break; end;
if flag then inc(f[j]);
end;
end;
for i:=1 to m do if f[i]=n then break;
m:=i;
for i:=1 to n do delete(a[i],m+1,maxlongint);
j:=0;p[1]:=0;
for i:=2 to n do
begin
while (j>0) and (a[i]<>a[j+1]) do j:=p[j];
if (a[i]=a[j+1]) then inc(j);
p[i]:=j;
end;
n:=n-p[n];
writeln(m*n);
end.