776. String shift inclusion problem

subject

For a string , Define a cyclic shift operation as ： Move the first character of a string to the end to form a new string .

Given two strings s1 and s2, It is required to determine whether one of the strings is a substring of the new string after the other string has been circularly shifted for several times .

for example CDAA By AABCD A new string produced after two shifts BCDAA The string of , and ABCD And ACBD You can't get that one of the strings is a substring of the new string through multiple shifts .

Input format
All in one line , Contains two strings , Separated by a single space .

The string contains only letters and numbers , Length not exceeding 30.

Output format
If a string is a substring of a new string generated by several cyclic shifts of another string , The output true, Otherwise output false.

sample input ：
AABCD CDAA
sample output ：
true

Ideas

Handwriting kmp Algorithm , Find String Problems , Copy and splice the string into double and then search the string, which is equivalent to the shift operation

Code

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100;

void get_next(char T[], int ne[])
{
    
    int n = strlen(T);
    ne[1] = 0;
    for(int i = 2, j = 0; i <= n; i++)
    {
    
        while(j && T[i] != T[j+1]) j = ne[j];
        if(T[i] == T[j+1]) j++;
        ne[i] = j;
    }
}

bool kmp(char T[], char S[])
{
    
    int ne[N] = {
    0};
    get_next(T, ne);
    
    int n = strlen(T+1);
    int m = strlen(S+1);
    for(int i = 1, j = 0; i <= m; i++)
    {
    
        while(j && S[i] != T[j+1]) j = ne[j];
        if(S[i] == T[j+1]) j++;
        if(j == n)
            return true;
    }
    return false;
}

int main()
{
    
    char S1[N], S2[N];
    
    cin >> S1+1 >> S2+1;

    char T1[N], T2[N];// Temporary storage S+1  and  S2+1 , The following string matches will be used as a string , T1+1 With the double S2+1 Match ,T2+1 With the double S1+1 Match 
    
    strcpy(T1+1,S1+1);//S1 Temporary presence T1, and S1 double 
    strcat(S1+1,T1+1);
    
    strcpy(T2+1,S2+1);//S2 Temporary presence T2, and S2 double 
    strcat(S2+1,T2+1);

    // Any string matches successfully 
    if (kmp(T1, S2) || kmp(T2, S1))puts("true");
    else puts("false");
    
    return 0;
}