大致题意:
求一个字符矩阵的最小覆盖子矩阵,输出这个子矩阵的面积。
大致题意:
关于一个字符串的最小覆盖子串可以看这里http://blog.csdn.net/fjsd155/article/details/6866991
接下来就是把子串扩展到二维,对行和列分别求出最小覆盖子串长度,相乘输出即可
#include<iostream>
#include<cstring>
#include<stack>
#include<cstdio>
using namespace std;
const int nMax=100005;
char pat[nMax][80];
int lenc,lenr,next[nMax];
int get_nextR(int c){
int i,j=-1;
next[0]=-1;
for(i=1;i<=lenr;i++){
while(j>-1&&pat[j+1][c]!=pat[i][c])j=next[j];
if(pat[j+1][c]==pat[i][c])j++;
next[i]=j;
}
// cout<<"next 2-"<<lenr-1-next[lenr-1]<<endl;
return lenr-1-next[lenr-1];
}
int get_nextC(int r){
int i,j=-1;
next[0]=-1;
for(i=1;i<=lenc;i++){
while(j>-1&&pat[r][j+1]!=pat[r][i])j=next[j];
if(pat[r][j+1]==pat[r][i])j++;
next[i]=j;
}
// cout<<"next c-"<<lenc-1-next[lenc-1]<<endl;
return lenc-1-next[lenc-1];
}
int getnum(int a,int b){ //求最小公倍数
// cout<<a<<" "<<b<<" ";
int c,d,e;
d=a;e=b;
do{c=a%b;a=b;b=c;}while(c!=0);
// cout<<d*e/a<<endl;
return d*e/a;
}
int main(){
int r,c,i,j,ans1,ans2;
while(scanf("%d%d",&lenr,&lenc)!=EOF){
ans1=1;
ans2=1;
for(i=0;i<lenr;i++){
scanf("%s",pat[i]);
}
for(i=0;i<lenr;i++){
memset(next,0,sizeof(next));
ans1=getnum(ans1,get_nextC(i));
if(ans1>=lenc){
ans1=lenc;
break;
}
}
for(i=0;i<lenc;i++){
memset(next,0,sizeof(next));
ans2=getnum(ans2,get_nextR(i));
if(ans2>=lenr){
ans2=lenr;
break;
}
}
cout<<ans1*ans2<<endl;
}
return 0;
}
分享到:
相关推荐
poj 上的几道kmp 题的解题报告 sourse code of kmp algorithm
kmp算法内容概况: 本文将介绍一种名为KMP的字符串匹配算法。KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为...
D-KMP体系结构-官方样本这是D-KMP架构的官方示例,展示了一个适用于Android和iOS的简单主/详细应用程序。 有关D-KMP体系结构的更多信息,请阅读相关的。D-KMP体系结构的主要功能: 它使用最新的声明性UI工具包:适用...
kmp算法内容概况: 本文将介绍一种名为KMP的字符串匹配算法。KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为...
KMP报告:元宇宙产品概念,哪一种消费者更有感 12.15-31页.pdf
KMP扩展器 适用于CSV文件的Mario Kart 7的KMP编辑器。
D-KMP架构Daniele Baroncelli建议的D-KMP体系结构的试用示例,位于: ://danielebaroncelli.medium.com/the-future-of-apps-declarative-uis-with-kotlin-multiplatform-d-kmp-part-1 它:声明性UI(Jetpack编写)...
kmp算法
模板-kmp-库 Kotlin多平台库模板。 有一个针对多平台库的基线设置,该库支持除弃用的wasm32之外的所有kotlin。 特征 本机目标分组和共享sourceSet 包装程序库模块,它声明对所有lib模块的依赖关系 通过allprojects...
kmp算法:查找一个字符串是不是另一个字符串的子串
算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP
kMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法Java...
KMP算法
DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法
KMP算法详解KMP算法详解KMP算法详解KMP算法详解KMP算法详解
KMP算法详解KMP算法详解KMP算法详解KMP算法详解
使用KMP算法实现模式匹配,包括next数组的求解,kmp算法的实现。关键代码有详细注释。
kmp(kangle+mysql+php)集成版,支持asp、asp.net、php脚本环境,集成mysql数据库和phpmyadmin管理工具。kmp包含组件:kangle 2.1.8mysql-5.5.8php-5.2.17ZendOptimizer-3.3.9phpmyadmin-3.3.9
\KMP 伪代码\KMP 伪代码\KMP 伪代码\KMP 伪代码\KMP 伪代码
扩展的KMP问题: 给定母串S,和子串T。 定义n=|S|, m=|T|,extend[i]=S[i..n]与T的最长公共前缀长度。请在线性的时间复杂度内,求出所有的extend[1..n]。