字符串移位包含问题

题意

判断两串中是否有一串是另一串循环移位若干次后得到的字符串的子串。

思路

选较长串为 longer，较短串为 shorter。所有 longer 的循环移位都能作为 longer + longer 中长度与原串相同的连续片段出现，因此只需判断 shorter in longer + longer。

代码

Python代码

python

1
2
3first, second = input().split()
longer, shorter = (first, second) if len(first) >= len(second) else (second, first)
print("true" if shorter in longer + longer else "false")

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36#include <cstdio>
#include <cstring>


char str1[500];
char str2[500];

int main(){
    scanf("%s",str1+1);
    scanf("%s",str2+1);
    int len1 = strlen(str1+1);
    int len2 = strlen(str2+1);
    
    char *s1 = str1,*s2=str2;
    if( len1 < len2){
        s1 = str2;
        s2 = str1;
    }
    len1 = strlen(s1+1);

    int i,j;
    if(  strstr(s1+1,s2+1) != NULL){
        printf("true");
        return 0;
    }
    for (i=2;i<=len1;i++){
        s1[len1+i-1] = s1[i-1];
        if( strstr(s1+i,s2+1) !=NULL){
            printf("true");
            return 0;
        }
    }
    printf("false");

    return 0;
}

复杂度

设较长串与较短串长度为 $n,m$ ，朴素匹配最坏时间复杂度为 $O(nm)$ ，额外空间为 $O(n)$ 。

总结

循环移位问题常可通过“原串拼接自身”转化为普通子串问题。

字符串移位包含问题

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结