题意:
这道题主要坑在题意上了><
Help FJ find the rectangular unit of smallest area that can be repetitively tiled to make up the entire milking grid. Note that the dimensions of the small rectangular unit do not necessarily need to divide evenly the dimensions of the entire milking grid,
as indicated in the sample input below.
求可以重复地平铺, 来构造出整个矩阵的矩形单元的最小面积.
小方格的尺寸并不一定要均匀地分割大矩形的尺寸.
意思就是,必须平铺, 但是右,下边缘的部分可以不考虑缺失.
可行的样例:
3 4
ABCA
DEFD
ABCA
输出:
6
但是, 这样不对齐是不可以的(大概这样不能算 repeat 吧,只有边缘才可以有例外!):
2 5
ABCDE
CDEAB
只能输出:
10
也就是不能有左边缺失的.
而且tile是不能有重叠覆盖的.
我鬼使神差地就将"dimension"yy成"direction", 总是在考虑反转啊神马的...误入歧途了.
(这一类的..各种不存在的条件我总是想太多! 题意啊题意!!!)
求最小重复子串,和power string 那题相比, 不同之处在于, 这题不要求最后一个子串是完整的.
//988K 547MS
#include<stdio.h>
#include<string.h>
char s[10010][80];
int next[10010];
int main()
{
int i,j,x,y,r,c,f[80];
char a[80];
scanf("%d%d",&r,&c);
memset(f,0,sizeof(f));
for(i=0; i<r; i++)//遍历每一行
{
scanf("%s",s[i]);
strcpy(a,s[i]);
//将每行的每种重复子串长度都求出来
for(j=c-1; j>0; j--)
{
a[j]=0;//从末尾一次减少一个字符的长度
for(x=0,y=0; s[i][y]; x++,y++)//y是目标串指针
{//x是模式串指针
if(!a[x])x=0;//如果模式串遍历结束, 就重新从头开始遍历
if(a[x]!=s[i][y])break;//一旦该长度的模式串无法以循环形式覆盖该行,跳出
}
if(!s[i][y])f[j]++;//如果是正常退出,那么长度j的模式串可以覆盖该行
}//将模式串的长度逐步缩短
}
for(i=0; i<c; i++) //找出所有行的最小相同的子串长度,为最小重复子矩阵的列数
if(f[i]==r)break;//f中记录的是相同长度(为i)的模式串(注意全都是左边顶头开始)
//在所有行中出现的频数,为r,即每一行都出现了.自然退出的话,i=c,适合于其他情况
x=i;//最小重复子矩阵的列数
for(i=0; i<r; i++)s[i][x]=0;//只考虑重复串即可,减小不必要的比较工作.
next[0]=-1;//按纵列求KMP的next函数，以求最小重复子矩阵的行数
for(i=1,j=-1; i<r; i++)
{
while(j!=-1&&strcmp(s[j+1],s[i]))j=next[j];
if(!strcmp(s[j+1],s[i]))j++;
next[i]=j;
}
printf("%d\n",(r-1-next[r-1])*x);//行列相乘即为最终结果
return 0;
}
自己实现一下:
统计所有可能的覆盖子串的时候也可以利用next 数组, len - 1 - next [ len - 1 ] 本身就忽视了结尾的不完整项(只是循环的字段视为右对齐, 但是长度不影响).
用这个公式算出的一定是最小覆盖子串, 那么求出覆盖次数后, 相乘便得到最大覆盖子串, 中间的均以整倍递增.
//984K 79MS
#include <cstring>
#include <cstdio>
const int R = 10005;
const int C = 80;
char s[R][C];
int next[R],f[C];
void prekmp(char pstr[])
{
next[0] = -1;
int j = -1;
for(int i=1;pstr[i];i++)
{
while(j!=-1 && pstr[j+1]!=pstr[i]) j = next[j];
if(pstr[j+1]==pstr[i]) j++;
next[i] = j;
}
}
int main()
{
int r,c,i,x;
scanf("%d %d",&r,&c);
for(i=0;i<r;i++)
{
scanf("%s",s[i]);
prekmp(s[i]);
int len = c - 1 - next[c-1];
int cnt = c / len;
for(int j=1;j<=cnt;j++)
f[len*j]++;
}
for(i=0;i<c;i++)
if(f[i]==r) break;
x = i;
for(i=0;i<r;i++)
s[i][x] = '\0';
next[0] = -1;
int j = -1;
for(i=1;i<r;i++)
{
while(j!=-1 && strcmp(s[j+1], s[i])) j = next[j];
if(!strcmp(s[j+1], s[i])) j++;
next[i] = j;
}
printf("%d\n",(r-1-next[r-1])*x);
}