【題目鏈接】

ybt 1140：驗證子串
OpenJudge NOI 1.7 18:驗證子串

【題目考點】

1. 字符串處理

2. 判斷子串（字符串模式匹配）

本文只給出的都是枚舉求子串的算法。假設要判斷長為n的字符串是不是長為m的字符串的子串，枚舉算法的復雜度為O((m-n)*n)
字符串模式匹配算法有KMP、BM、Sunday、Horspool等等，如想學習，可以自行搜索。

3. 查找子串函數

c++庫函數中存在查找一個字符串在另一個字符串中出現位置的函數，該函數自然也可以用來判斷一個字符串是否是另一個字符串的子串。

• 字符數組查找子串：<cstring>中包含函數：
  strstr (s1, s2);
  其中參數s1、s2是字符數組
  返回值：此函數返回一個指針，該指針指向s1中找到的s2的第一個字符，如果s1中不存在s2，則返回空指針。
• string類查找子串：
  s1.find(s2)
  其中s1，s2是string類對象。
  返回值：是一個無符號整數，為s2在s1中第一次出現的位置。
  如s2不是s1的子串，那么返回string::npos（靜態變量，值為-1u或unsigned(-1))
  (find函數用法有很多，這里只給出一種)

【解題思路】

解法1：枚舉判斷子串

1）使用字符數組

首先比較兩個字符串的長短，若s1的長度大于等于s2的長度，則不操作。如果s1的長度小于s2的長度，那么將s1與s2的值交換。保持s1的長度大于等于s2的長度。此時只需檢測s2是否是s1的子串。

遍歷s1，設變量j，j表示現在看s2的哪一個字符。不斷比較s1[i]與s2[j]，若二者相同，j增加1，比較后一個字符。若二者不同，j歸0。若j的值已經增加至s2的長度，說明s1中存在完整的s2的字符串，那么s2是s1的子串。

2）使用string類
思路與上述方法基本相同。可以使用string類的成員函數substr(起始位置，截取長度)在s1中截取部分字符串，然后和s2比較。

解法2：使用查找子串的函數

• 如使用字符數組，用strstr函數
• 如使用string類，用find成員函數

【題解代碼】

解法1：枚舉判斷子串

• 字符數組

#include<bits/stdc++.h> using namespace std; #define N 205 bool isSubStr(char s1[], char s2[])//枚舉判斷s2是不是s1的子串 {int l1 = strlen(s1), l2 = strlen(s2);for(int i = 0; i <= l1-l2; ++i){//判斷s1從s1[i]~s1[i+l2-1]是否與s2相同 bool isSame = true;for(int j = 0; j < l2; ++j){if(s1[i+j] != s2[j]){isSame = false;break;}}if(isSame)return true;}return false; } int main() {char s1[N], s2[N], t[N];cin >> s1 >> s2;int l1 = strlen(s1), l2 = strlen(s2);if(l1 < l2)//保證s1更長 {strcpy(t, s1);strcpy(s1, s2);strcpy(s2, t);swap(l1, l2);}if(isSubStr(s1, s2))cout << s2 << " is substring of " << s1;elsecout << "No substring";return 0; }

• string類

#include<bits/stdc++.h> using namespace std; bool isSubStr(string s1, string s2)//s2是不是s1的子串 {int l1 = s1.length(), l2 = s2.length();for(int i = 0; i <= l1 - l2; ++i){if(s1.substr(i, l2) == s2)return true;}return false; } int main() {string s1, s2;cin >> s1 >> s2;if(s1.length() < s2.length())swap(s1, s2);if(isSubStr(s1, s2))cout << s2 << " is substring of " << s1;elsecout << "No substring";return 0; }

解法2：使用查找子串的函數

• 使用字符數組，用strstr函數

#include<bits/stdc++.h> using namespace std; #define N 205 int main() {char s1[N], s2[N], t[N];cin >> s1 >> s2;int l1 = strlen(s1), l2 = strlen(s2);if(l1 < l2)//保證s1更長 {strcpy(t, s1);strcpy(s1, s2);strcpy(s2, t);swap(l1, l2);}if(strstr(s1, s2) == NULL)cout << "No substring";elsecout << s2 << " is substring of " << s1;return 0; }

• 使用string類，用find成員函數

#include<bits/stdc++.h> using namespace std; int main() {string s1, s2;cin >> s1 >> s2;if(s1.length() < s2.length())swap(s1, s2);if(s1.find(s2) == string::npos)cout << "No substring";elsecout << s2 << " is substring of " << s1;return 0; }

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1140：验证子串 | OpenJudge NOI 1.7 18的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。