首页 > 代码库 > Substrings

Substrings

2024-07-13 05:41:34   219人阅读

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 }
View Code


联系
我们