传送门:http://poj.org/problem?id=3450
题目大意:前面那道题类似,求多个字符串的最长且字典序最小的公共子串,还是枚举子串,然后拿去和剩余主串匹配,保存最优解。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 222,MAXM = 4444;
char s[MAXM][MAXN],temp[MAXN],res[MAXN];
int next[MAXN],n;
void makenext(char *str){
int i = 0,j = -1,M = strlen(str);
next[0] = -1;
while(i<M){
if(str[i]==str[j]||j==-1)next[++i] = ++j;
else j = next[j];
}
}
int KMP(char *T,char *P){
int N = strlen(T),M = strlen(P),i = 0,j = 0;
while(i<N&&j<M){
if(T[i]==P[j]||j==-1)i++,j++;
else j = next[j];
}
return j==M?i-M:-1;
}
bool great(char *s1,char *s2){
int l1 = strlen(s1),l2 = strlen(s2);
if(l1!=l2)return l1>l2;
return strcmp(s1,s2)<0;
}
int main(){
while(scanf("%d",&n),n){
for(int i=0;i<n;i++)scanf("%s",s[i]);
int l = strlen(s[0]);res[0] = 0;
for(int i=0;i<l;i++){
for(int j=i;j<l;j++){
for(int k=0;k<j-i+1;k++){
temp[k] = s[0][k+i];
}
temp[j-i+1] = 0;
makenext(temp);
int ok = 1;
for(int k=1;k<n;k++){
if(KMP(s[k],temp)==-1){
ok = 0;break;
}
}
//cout<<temp<<" "<<ok<<endl;
if(ok&&great(temp,res)){
strcpy(res,temp);
}
}
}
if(res[0]){
printf("%s\n",res);
}else{
printf("IDENTITY LOST\n");
}
}
return 0;
}
分享到:
相关推荐
poj 上的几道kmp 题的解题报告 sourse code of kmp algorithm
kmp算法解决pku的3450题 //求4000个长度为200的串的最长公共字串(LCS)长度
算法 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算法详解KMP算法详解KMP算法详解KMP算法详解KMP算法详解
KMP算法详解KMP算法详解KMP算法详解KMP算法详解
\KMP 伪代码\KMP 伪代码\KMP 伪代码\KMP 伪代码\KMP 伪代码
数据结构中KMP算法过程的Flash演示
KMP算法实现 KMP算法实现 KMP算法实现 KMP算法实现
基于KMP算法的字符串匹配源码, 支持通配符,单匹配和多重匹配。 效率比较高
数据结构、kmp算法、代码实现、KMP(char *P,char *T,int *N,int start)
用C++语言实现的KMP算法。经过调试。供广大算法学习者参考。
用于字符串匹配的最新型算法,可提高性能,替代传统的contains算法这种暴力匹配算法,可用于实际开发,亦可用于学习,有兴趣的随便拿去用
此程序配合清华大学出版《数据结构(C语言版)》 P83-84页的KMP算法 win tc调试通过
KMP算法是通过分析子串,预先计算每个位置发生不匹配的时候,所需GOTO的下一个比较位置,整理出来一个next数组,然后在上面的算法中使用。
poj的代码,KMP没什么难度算法易证。
kmp算法:查找一个字符串是不是另一个字符串的子串
易语言KMP算法模块源码,KMP算法模块,kmp_init,kmp_find,字节集_子字节集寻找
使用并行计算编程工具OpenMp实现kmp串匹配