验证子串

题意

判断两条字符串中是否有一条是另一条的子串，并按指定格式输出关系。

思路

first in second 直接判断第一串是否为第二串子串；若不成立，再检查相反方向。两个方向都不成立时输出 No substring。

代码

Python代码

python

1
2
3
4
5
6
7
8
9first = input().strip()
second = input().strip()

if first in second:
    print(f"{first} is substring of {second}")
elif second in first:
    print(f"{second} is substring of {first}")
else:
    print("No substring")

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21#include <cstdio>
#include <cstring>


char str1[1000];
char str2[1000];
int main(){
    scanf("%s",str1);
    scanf("%s",str2);

    if( strstr(str1,str2) != NULL){
        printf("%s is substring of %s",str2,str1);
    }
    else if( strstr(str2,str1) != NULL){
        printf("%s is substring of %s",str1,str2);
    }
    else
        printf("No substring");

    return 0;
}

复杂度

朴素子串匹配最坏时间复杂度为 $O(nm)$ ，额外空间复杂度为 $O(1)$ 。

总结

Python 的 in 是最直观的子串存在性写法。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结