POJ 2185(最大平铺矩阵）

Posted on by
内容目录
Language:
Milking Grid
Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 4346   Accepted: 1780

Description

给定R(1 <= R <= 10,000) *C (1 <= C <= 75) 的矩阵，求它的最大平铺矩阵,不够的地方可部分平铺，但不可重叠。

Input

第一行：R和C.
第2-R+1行每行C个大写字母，表示矩阵.

Output

最大的平铺矩阵面积

Sample Input

2 5
ABABA
ABABA

Sample Output

2

Hint

The entire milking grid can be constructed from repetitions of the pattern 'AB'.

Source

USACO 2003 Fall

显然这个矩阵必然从左上角开始

由于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.