验证子串

题目描述

输入两个不含空格的字符串 $s_1, s_2$ （每行一个，长度不超过 200）。若 $s_1$ 是 $s_2$ 的连续子串，输出 s1 is substring of s2；否则，若 $s_2$ 是 $s_1$ 的子串，输出 s2 is substring of s1；否则输出 No substring。如输入 abc、dddncabca，则输出 abc is substring of dddncabca。

思路

枚举 $s_2$ 的每个起点 $k$ ，比较长度为 $|s_1|$ 的窗口 $s_2[k:k+|s_1|]$ 是否整段等于 $s_1$ 。分支必须先判 $s_1 \sqsubseteq s_2$ 、后判 $s_2 \sqsubseteq s_1$ ，两串全等时才能输出方向一。长度不超过 200，朴素 $O(|s_1| \cdot |s_2|)$ 足够。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 20:38
# update_at: 2026-10-04 12:56

import sys


def solve() -> None:
    data = iter(sys.stdin.read().split())
    s1, s2 = next(data), next(data)

    # 按题面顺序问两次：先问 s1 是否为 s2 的子串，再问反向，两次都没命中才是 No substring
    if s1 in s2:
        print(f"{s1} is substring of {s2}")
    elif s2 in s1:
        print(f"{s2} is substring of {s1}")
    else:
        print("No substring")


if __name__ == "__main__":
    solve()

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
37
38
39
40
41
42
43
44/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 03:21
 * update_at: 2026-10-05 03:21
 */

#include <cstdio>
#include <cstring>

typedef long long ll;

const int MAXN = 205;

char s1[MAXN]; // 第一个字符串
char s2[MAXN]; // 第二个字符串

// 判断模式串 p（长度 lp）是否为文本串 t（长度 lt）的连续子串
bool is_substring(char t[], ll lt, char p[], ll lp) {
    if (lp > lt) return false; // 子串不可能比母串长
    for (ll k = 0; k + lp <= lt; k++) { // 枚举起点 k，比较窗口 t[k:k+lp]
        ll j = 0;
        while (j < lp && t[k + j] == p[j]) j++;
        if (j == lp) return true; // 整段窗口匹配成功
    }
    return false;
}

int main() {
    scanf("%s%s", s1, s2);
    ll n = strlen(s1);
    ll m = strlen(s2);

    // 按题面顺序：先判 s1 是否为 s2 的子串，再反过来判，最后输出 No substring
    if (is_substring(s2, m, s1, n)) {
        printf("%s is substring of %s\n", s1, s2);
    } else if (is_substring(s1, n, s2, m)) {
        printf("%s is substring of %s\n", s2, s1);
    } else {
        printf("No substring\n");
    }
    return 0;
}

目录

题目描述

思路

参考代码