驗證子串

題目描述

輸入兩個字符串，驗證其中一個串是否為另一個串的子串。

輸入格式

兩行，每行一個字符串。

輸出格式

若第一個串 $s_1$ 是第二個串 $s_2$ 的子串，則輸出(s1) is substring of (s2)；

否則，若第二個串 $s_2$ 是第一個串 $s_1$ 的子串，輸出(s2) is substring of (s1)；

否則，輸出 No substring。

樣例 #1

樣例輸入 #1

abc
dddncabca

樣例輸出 #1

abc is substring of dddncabca

樣例 #2

樣例輸入 #2

aaa
bbb

樣例輸出 #2

No substring

提示

對于 $100\%$ 的數據，字符串長度在 $20$ 以內。

方法1

解題思路:

本題要求我們驗證兩個字符串之間的子串關系。我們可以使用字符串的 find 函數來判斷一個字符串是否為另一個字符串的子串。find 函數會返回子串在主串中第一次出現的位置,如果找不到子串,則返回一個特殊值 string::npos。

具體步驟如下:

1. 讀取兩個字符串 $s_1$ 和 $s_2$。
2. 使用 find 函數判斷 $s_1$ 是否為 $s_2$ 的子串:
   • 如果 s2.find(s1) != string::npos,則 $s_1$ 是 $s_2$ 的子串,輸出 (s1) is substring of (s2)。
   • 否則,繼續下一步。
3. 使用 find 函數判斷 $s_2$ 是否為 $s_1$ 的子串:
   • 如果 s1.find(s2) != string::npos,則 $s_2$ 是 $s_1$ 的子串,輸出 (s2) is substring of (s1)。
   • 否則,繼續下一步。
4. 如果以上條件都不滿足,說明兩個字符串之間沒有子串關系,輸出 No substring。

C++代碼實現:

#include <iostream>
#include <string>
using namespace std;int main() {string s1, s2;cin>>s1;cin>>s2;if (s2.find(s1) != string::npos) {cout << s1 << " is substring of " << s2 << endl;} else if (s1.find(s2) != string::npos) {cout << s2 << " is substring of " << s1 << endl;} else {cout << "No substring" << endl;}return 0;
}

代碼解釋:

1. 使用 getline 函數讀取兩個字符串 $s_1$ 和 $s_2$,每個字符串占一行。
2. 使用 s2.find(s1) != string::npos 判斷 $s_1$ 是否為 $s_2$ 的子串:
   • 如果條件成立,說明 $s_1$ 是 $s_2$ 的子串,使用 cout 輸出 s1 is substring of s2。
   • 否則,繼續下一步。
3. 使用 s1.find(s2) != string::npos 判斷 $s_2$ 是否為 $s_1$ 的子串:
   • 如果條件成立,說明 $s_2$ 是 $s_1$ 的子串,使用 cout 輸出 s2 is substring of s1。
   • 否則,繼續下一步。
4. 如果以上條件都不滿足,說明兩個字符串之間沒有子串關系,使用 cout 輸出 No substring。

復雜度分析:

• 時間復雜度:$O(n\times m)$,其中 $n$ 和 $m$ 分別是兩個字符串的長度。在最壞情況下,需要遍歷兩個字符串的所有可能的子串組合。
• 空間復雜度:$O(1)$。只使用了常數級別的額外空間。

該解決方案利用了 find 函數快速判斷子串關系,避免了手動實現子串匹配的過程。通過兩次判斷,我們可以確定兩個字符串之間的子串關系,并輸出相應的結果。