先对每行求出所有可能的循环节长度(不需要整除)。

然后取在所有行中都出现了的,且最小的长度为宽。

然后将每一行看作字符,对所有行求next数组,将n-next[n](对这些行来说最小的循环节长度)作为长。

最后输出长乘宽即可。

#include<cstdio>
#include<cstring>
using namespace std;
bool can[10010][80];
char s[10010][80];
int next[80],n,m,wide,NEXT[10010];
void GetFail(char P[],int next[])//next[i]表示s[0]~s[i-1]的前缀中,最大相等的前后缀的长度是多少
{
next[0]=-1;
int len=strlen(P);
for(int i=0;i<len;i++)
{
int j=next[i];
while(j>=0 && P[i]!=P[j])
j=next[j];
if(j!=-1 && P[i]==P[j])
next[i+1]=j+1;
else next[i+1]=0;
}
}
int main()
{
// freopen("poj2185.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i)
{
scanf("%s",s[i]);
GetFail(s[i],next);
for(int j=next[m];j!=-1;j=next[j])
can[i][m-j]=1;
}
for(int j=1;j<=m;++j)
{
bool flag=1;
for(int i=0;i<n;++i)
if(!can[i][j])
{
flag=0;
break;
}
if(flag)
{
wide=j;
break;
}
}
for(int i=0;i<n;++i)
s[i][wide]='\0';
next[0]=-1;
int len=n;
for(int i=0;i<len;i++)
{
int j=next[i];
while(j>=0 && strcmp(s[i],s[j])!=0)
j=next[j];
if(j!=-1 && strcmp(s[i],s[j])==0)
next[i+1]=j+1;
else next[i+1]=0;
}
printf("%d\n",wide*(n-next[n]));
return 0;
}

最新文章

  1. markdown语法与使用
  2. GetEnumerator();yield
  3. App瘦身
  4. CSS 自定义字体
  5. 技术文档--volley 框架
  6. IOS中用UIStoryBoard类初始化/跳转控制器
  7. PLSQL_Oracle Logon Trigger的建立
  8. 项目上线与LOG记录
  9. 在Ubuntu上为Android系统的Application Frameworks层增加硬件访问服务(老罗学习笔记5)
  10. swift-01-简述swift与OC区别
  11. linux中nginx的安装,linux的版本是ubutu
  12. PAT 团体程序设计天梯赛-练习集 L1-023. 输出GPLT
  13. office web apps 部署-搭建域控服务器
  14. java.lang.IllegalArgumentException异常 返回值类型的问题
  15. springdata 一对多配置
  16. bzoj千题计划321:bzoj5251: [2018多省省队联测]劈配(网络流 + 二分)
  17. SQL Server In-Memory OLTP Internals for SQL Server 2016
  18. FSMC_LCD
  19. MFC字体样式和颜色设置
  20. RecyclerView通用适配器

热门文章

  1. BZOJ 2457 双端队列(思维
  2. C# new override
  3. 打砖块(codevs 1257)
  4. MDK stm32 仿真
  5. 【洛谷 P1337】[JSOI2004]平衡点 / 吊打XXX (模拟退火)
  6. [bzoj2002][Hnoi2010]Bounce弹飞绵羊——分块
  7. SELinux 案例 2
  8. [Leetcode Week6]Linked List Cycle II
  9. [Leetcode Week4]Merge Two Sorted Lists
  10. Java坦克大战 (五) 之产生敌方坦克和爆炸效果