admin管理员组文章数量:1615702
题目链接:http://acm.hdu.edu/showproblem.php?pid=2328
找一个字典序最小的公共最长子串,枚举子串暴力就能过,这里有个小优化就是选取最短的字符串枚举其子串。
#include <stdio.h>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
char p[205][205];
char str1[205];
int len[205];
char ast[205];
int nxt[205];
void gnx(char str[],int len){
memset(nxt,0,sizeof(nxt));
int i=0,j=-1;
nxt[0]=-1;
while(i<len){
if(j==-1||str[i]==str[j]){
if(str[++i]==str[++j])nxt[i]=nxt[j];
else nxt[i]=j;
}
else j=nxt[j];
}
}
int kmp(char s[],int ls,char p[],int lp){
int i=0,j=0;
while(i<ls&&j<lp){
if(j==-1||s[i]==p[j]){++i;++j;}
else j=nxt[j];
}
if(j==lp)return i-lp;
else return -1;
}
int sstrcmp(char a[],char b[],int len){
int i=0;
while(i<len){
if(a[i]<b[i])return -1;
else if(a[i]>b[i])return 1;
else i++;
}
return 0;
}
int main(void)
{
int n;
while (~scanf("%d", &n) && n)
{
int ans = 0;
int st = 0, mn = 1000;
for (int i = 1; i <= n; i++)
{
scanf("%s", p[i]);
len[i] = strlen(p[i]);
if (len[i] < mn)
{
mn = len[i];
st = i;
}
}
for(int i=0;i<mn;i++){
memcpy(str1,p[st]+i,mn-i);
str1[mn-i]=0;
gnx(str1,mn-i);
for(int j=max(ans,1);j<=mn-i;j++){
int flag=1;
for(int k=1;k<=n;k++){
if(k==st)continue;
if(kmp(p[k],len[k],str1,j)==-1){flag=0;break;}
}
if(flag){
if(j>ans||((j==ans)&&sstrcmp(ast,str1,j)>0)){ans=j;memcpy(ast,str1,j);ast[j]=0;}
}
}
}
if(ans==0)puts("IDENTITY LOST");
else printf("%s\n",ast);
}
return 0;
}
本文标签: hdu2328CorporateIDENTITY
版权声明:本文标题:hdu2328Corporate Identity 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1728724670a1170598.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论