本题枚举每行的宽度,因为每行字符串不是完美字符串,所以不能用kmp来做,然后对高度做kmp,即n-ne[n],最后相乘
C++ 代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1e4+10,M=80,INF=1e8;
int n,m,ne[N],judge[N];
char str[N][M];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",str[i]);
for(int j=1;j<=m;j++)
{
if(!judge[j])
{
for(int k=j;k<=m;k+=j)
{
for(int u=0;u<j&&k+u<m;u++)
{
if(str[i][u]!=str[i][u+k])
{
judge[j]=1;
break;
}
}
if(judge[j]) break;
}
}
}
}
int len;
for(int i=1;i<=m;i++)
{
if(!judge[i]) {len=i;break;}
}
for(int i=1;i<=n;i++) str[i][len]=0;
for(int i=2,j=0;i<=n;i++)
{
while(j&&strcmp(str[i],str[j+1])) j=ne[j];
if(!strcmp(str[i],str[j+1])) j++;
ne[i]=j;
}
int len2=n-ne[n];//行的最小循环节
printf("%d",len2*len);
return 0;
}