首页 > 代码库 > 亲和串

亲和串

2024-07-13 02:45:16   214人阅读

hdu2203:http://acm.hdu.edu.cn/showproblem.php?pid=2203

题意：给定两个字符串s1和s2,如果能通过s1循环移位，使s2包含在s1中，那么我们就说s2 是s1的亲和串。

题解：把s1拼接两遍，然后直接用KMP搞定。例如 s1=abcd,s2==bcda,可以把s1=abcdabcd,然后查找。但是这里有一个要求就s1的长度如果比s2短的话，就肯定不行，直接输出，不能这样判断。因为会存在这种情况。s1=abcd s2=abcda,这样，如果这样判断的话，就会得到相反的答案。

 1 #include<stdio.h> 2 #include<string.h> 3 #define N 100005 4 int next[N]; 5 int flag,len2,len1; 6 char str1[2*N],str2[N]; 7 void getnext(int plen){ 8     int i = 0,j = -1; 9     next[0] = -1;10     while( i<plen ){11         if(j==-1||str2[i]==str2[j]){12             ++i;++j;13           if(str2[i]!=str2[j] )14             next[i] = j;15           else16             next[i] = next[j];17         }18         else19             j = next[j];20     }21 }22 int  KMP(){23     getnext(len2);24     int i = 0,j = 0;25     int ct=0;26     while (i<len1&&j<len2){27         if( j == -1 || str1[i] == str2[j] ){28             ++j;29             i++;30         }31         else {32             j = next[j];33         }34     }35     if(j>=len2)return 1;36     else37       return 0;38 }39 int main()40 {41     int i,j,k;42     while(scanf("%s%s",str1,str2)!=EOF){43         flag=-1;44         len1=strlen(str1);45         len2=strlen(str2);46         if(len1<len2){47           printf("no\n");48             continue;49         }50         for(i=0;i<len1;i++)51             str1[i+len1]=str1[i];52         str1[len1*2]=‘\0‘;53         len1=len1*2;54         flag=KMP();55         if(flag==1) printf("yes\n");56         else printf("no\n");57     }58     return 0;59 }
View Code

看了别人的代码，发现c++里面有一个函数strstr(str1,str2),可以用来查找，int num=strstr(str1,str2)-str1;,num表示str2在str1第一次出现的下标。没有找到会得到一个负数。

 1 #include<algorithm> 2 #include <cstring> 3 #include<cstdio> 4 #include<iostream> 5 using namespace std; 6 int main(){ 7 char str[100000]; 8 char str1[100000]; 9 char str2[200000];10 while ( gets(str) ) {11    gets(str1);12    strcpy(str2, str);13    strcat(str2, str);14    if ( strstr(str2, str1) != NULL ) {15     puts("yes");16    }else {17     puts("no");18    }19 }20 return 0;21 22 }
View Code


联系
我们