776. 字符串移位包含问题

题目

对于一个字符串来说，定义一次循环移位操作为：将字符串的第一个字符移动到末尾形成新的字符串。

给定两个字符串 s1 和 s2，要求判定其中一个字符串是否是另一字符串通过若干次循环移位后的新字符串的子串。

例如 CDAA 是由 AABCD 两次移位后产生的新串 BCDAA 的子串，而 ABCD 与 ACBD 则不能通过多次移位来得到其中一个字符串是新串的子串。

输入格式
共一行，包含两个字符串，中间由单个空格隔开。

字符串只包含字母和数字，长度不超过 30。

输出格式
如果一个字符串是另一字符串通过若干次循环移位产生的新串的子串，则输出 true，否则输出 false。

输入样例：
AABCD CDAA
输出样例：
true

思路

手写kmp算法，查找字串问题，将字符串复制拼接成双倍再进行字串查找即可相等于移位操作

代码

#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];//临时保存S+1 和 S2+1 ,后面字符串匹配都会作为字串， T1+1跟双倍后的S2+1进行匹配，T2+1跟双倍后的S1+1进行匹配
    
    strcpy(T1+1,S1+1);//S1临时存在T1,而S1双倍
    strcat(S1+1,T1+1);
    
    strcpy(T2+1,S2+1);//S2临时存在T2,而S2双倍
    strcat(S2+1,T2+1);

    //任意一个字串匹配成功即可
    if (kmp(T1, S2) || kmp(T2, S1))puts("true");
    else puts("false");
    
    return 0;
}