1 #include<iostream> 2 #include<cstring> 3 //.size()的头文件 4 using namespace std; 5 6 int next1[1000005]; 7 void getnext(string t ,int tsize)//从0号下标开始存起 8 { 9 int len = -1 ; 10 int j = 0; 11 next1[0] = -1; 12 while(j<tsize-1) 13 { 14 if(len==-1||t[j] == t[len]) 15 { 16 ++j; 17 ++len; 18 next1[j] = len; 19 // cout<<next1[j]<<" "; 20 }else 21 len = next1[len]; 22 } 23 } 24 25 int kmp(string s ,string t ,int ssize,int tsize)//字符串都是从0号下标开始存起 26 { 27 int i = 0 ; 28 int j = 0 ; 29 while(i<ssize&&j<tsize) 30 { 31 if(j==-1||s[i]==t[j]) 32 { 33 i++; 34 j++; 35 } 36 else 37 { 38 j = next1[j]; 39 } 40 } 41 if(j==tsize) 42 { 43 return i-j+1; 44 }else 45 return -1; 46 } 47 48 int n ; 49 int ssize; 50 int tsize; 51 int ans ; 52 int main() 53 { 54 int flag = 0; 55 char s[100000]={0},t[100000] = {0},temp_tt[10000] = {0}; 56 57 cin>>n; //输入要检测的病毒串和人串 58 while(n--) 59 { 60 61 cin>>t; //病毒序列 62 tsize = strlen(t); 63 64 for(int i = 0;i<tsize;i++)//把子串加倍:病毒是环状的 65 { 66 t[tsize+i] = t[i]; 67 } 68 t[tsize*2] = '\0'; 69 70 cin>>s;//人体的字符串 71 ssize = strlen(s); 72 73 for(int j = 0;j<tsize;j++) 74 { 75 string temp = t; 76 temp.copy(temp_tt, tsize, j); //把加倍的字符串temp切片:切为长度为tsize,起点下标为j的字符数组,并把他放在temp_tt中 77 getnext(temp_tt,tsize); 78 ans = kmp(s,temp_tt,ssize,tsize); //用一个ans来记录是否找到匹配 79 if(ans!=-1) //找到 80 { 81 flag++; 82 break; 83 } 84 } 85 if(!flag) 86 cout<<"NO"<<endl; 87 else 88 cout<<"YES"<<endl; 89 flag = 0; 90 } 91 return 0; 92 }