首页 > 代码库 > Substrings
Substrings
hdu1238:http://acm.hdu.edu.cn/showproblem.php?pid=1238
题意:给你n个串,求一个子串,这个子串在所有串中都出现,或者在逆串中出现。求最大的这个子串长度。
题解:分析一下,这个子串肯定会在最短的串中出现,所以,枚举最小串的所有子串,并且从最大的子串开始,看看这个子串是否出现在剩余的所有串中。查询剩余串的话,可以用KMP搞一下。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #define N 205 5 using namespace std; 6 int next[N]; 7 int n; 8 char s1[N];//模板串 9 char s2[N];//主串10 int len1,len2,ans;11 char str[120][N];12 void getnext(int plen){13 int i = 0,j = -1;14 next[0]=-1;15 while( i<plen ){16 if(j==-1||s1[i]==s1[j]){17 ++i;++j;18 if(s1[i]!=s1[j] )19 next[i] = j;20 else21 next[i] = next[j];22 }23 else24 j = next[j];25 }26 }27 bool KMP(){28 int i = 0,j = 0;29 while (i<len2&&j<len1){30 if( j == -1 || s2[i] == s1[j] ){31 ++i;32 ++j;33 }34 else {35 j = next[j];36 }37 }38 if(j>=len1)return true;39 else40 return false;41 }42 int main(){43 int cas;44 scanf("%d",&cas);45 while(cas--){46 scanf("%d",&n);47 int pos=-1,minn=200,ans=0;48 bool flag=false;49 for(int i=1;i<=n;i++){50 scanf("%s",&str[i]);51 int len=strlen(str[i]);52 if(len<minn){53 minn=len;pos=i;54 }55 }56 for(int i=minn;i>=1;i--){57 for(int j=0;j+i<=minn;j++){58 memset(s1,0,sizeof(s1));59 for(int k=j;k<j+i;k++){60 s1[k-j]=str[pos][k];61 }62 // printf("**%s\n",s1);63 len1=i;64 getnext(i);65 int g;66 for(g=1;g<=n;g++){67 strcpy(s2,str[g]);68 int temp=strlen(str[g]);69 len2=temp;70 if(KMP())continue;71 else{72 for(int m=0;m<temp;m++)73 s2[m]=str[g][temp-m-1];74 if(!KMP())break;75 }76 }77 if(g>n){flag=true;break;}78 }79 if(flag){ans=i;break;}80 81 }82 printf("%d\n",ans);83 84 }85 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。