水题不多说,循环位移就是将两个这样的串相连,看子串是不是这个相连的串的子串,是的就是亲和串。因为如果是在原串最后一个开始匹配正确,那么下一个就要到原串的第一个去匹配,因此需要两串相连。而又因为是循环位移,所以长度不会超过两倍原串。
贴码:
KMP:
#include <iostream> #include <string.h> #include <stdio.h> using namespace std; #define MAXV 100001 char str[MAXV],substr[MAXV],s[MAXV]; int next[MAXV]; int len1,len2; void compute_next() { int i,j; i=0; next[0]=-1; j=-1; while(i < len2-1) { if(j == -1 || substr[i] == substr[j]) { i++; j++; //修正的地方就发生下面这4行 if(substr[i] != substr[j] ) next[i] = j; else next[i] = next[j]; } else { j = next[j]; } } } int KMP(int pos) { int i, j; i = pos; j = 0; while(str[i] != 0 && j < len2) { if(j == -1 || substr[j] == str[i]) { i++; j++; } else { j = next[j]; } } if(j == len2) return i - j; else return -1; } int main() { while(~scanf("%s%s",s,substr)) { len1 = strlen(s); strcpy(str,s); strcat(str,s); len2 = strlen(substr); len1 = strlen(str); compute_next(); if(KMP(0) != -1) printf("yes\n"); else printf("no\n"); } return 0; }
strstr():
#include <iostream> #include <string.h> #include <stdio.h> using namespace std; #define MAXV 100001 char str[MAXV],substr[MAXV],s[MAXV]; int main() { while(~scanf("%s%s",s,substr)) { strcpy(str,s); strcat(str,s); if(strstr(str,substr)) printf("yes\n"); else printf("no\n"); } return 0; }