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 else
16 next[i] = next[j];
17 }
18 else
19 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 else
37 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("non");
48 continue;
49 }
50 for(i=0;i<len1;i++)
51 str1[i+len1]=str1[i];
52 str1[len1*2]=' ';
53 len1=len1*2;
54 flag=KMP();
55 if(flag==1) printf("yesn");
56 else printf("non");
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原文链接: https://www.cnblogs.com/chujian123/p/3857263.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/138520
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!