解题思路

题目要我们判断：s1 和 s2 这两个字符串，谁是谁的子串。

判断的方法很简单：在一个字符串里找另一个字符串。用 C++ 的 find：

• s2.find(s1) 在 s2 里找 s1，找到了就说明 s1 是 s2 的子串；
• find 找不到会返回 string::npos，所以判断“不是 string::npos”就是“找到了”。

按题目的优先级：

1. 先看 s1 是不是 s2 的子串（在 s2 里找 s1）；
2. 如果不是，再看 s2 是不是 s1 的子串（在 s1 里找 s2）；
3. 两个都不是，输出 No substring。

注意输出格式里的小括号里装的是字符串本身：

• s1 是 s2 的子串，输出 (s1) is substring of (s2)。

用样例验证：s1=abc，s2=dncabca。在 s2 里找 abc，从第 4 个字符开始正好是 abc，所以输出 abc is substring of dncabca，和样例一致。

参考代码

// P4553 验证子串：判断两个字符串谁是谁的子串
#include <iostream>
#include <string>
using namespace std;
int main() {
    string s1, s2;
    cin >> s1 >> s2;
    // s1在s2里能找到，说明s1是s2的子串
    if (s2.find(s1) != string::npos)
        cout << s1 << " is substring of " << s2 << endl;
    // 否则看s2是不是s1的子串
    else if (s1.find(s2) != string::npos)
        cout << s2 << " is substring of " << s1 << endl;
    else
        cout << "No substring" << endl;
    return 0;
}

复杂度分析

• 两个字符串长度都不超过 20，find 一次最多比较 20×20=400 次。
• 总时间复杂度 O(len(s1) × len(s2))，常数很小；
• 空间复杂度 O(1)。