【題目鏈接】

ybt 2050：【例5.20】字串包含
OpenJudge NOI 1.17 19:字符串移位包含問題

【題目考點】

1. 字符串

2. 判斷一個字符串是不是另一個字符串的子串（字符串模式匹配）

字符串模式匹配有多種算法，如：KMP、BM、Sunday、Horspool等等，如想學(xué)習(xí)，可以自行搜索。
本文只給出最基本的枚舉法，來判斷一個字符串是不是另一個字符串的子串。

• 字符數(shù)組

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; }

• string類:

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; }

3. 查找子串函數(shù)

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

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

【解題思路】

解法1 ：循環(huán)遍歷并比較

先確定輸入的兩個字符串哪個更長哪個更短，設(shè)更長的為s1，更短的為s2。其中s1的長度為l1，s2的長度為l2。判斷s2是否可以是s1的子串。
嘗試從s1的每個位置出發(fā)，循環(huán)遍歷向后數(shù)l2個字符（如果到末尾，就回到第0位置繼續(xù)數(shù)），看這l2個字符和s2是否相同。如果存在相同的情況，那么s1位移包含s2，輸出true。如果不存在相同的情況，輸出false。

解法2： 構(gòu)造新字符串并判斷子串

先讓s1是較長的字符串，s2是較短的字符串。s1長度l1，s2長度l2。
讓s1做l1次循環(huán)移位（每個字符向左移位一次，第0個字符移位到最后），每次得到一個新字符串s1，判斷s2是否是這個新的s1的子串。判斷一個字符串是否是另一個字符串的子串，參考【題目考點】3、4，可以用自己寫的函數(shù)，也可以用c++庫中存在函數(shù)。

【題解代碼】

解法1：循環(huán)遍歷并比較

#include<bits/stdc++.h> using namespace std; int main() {char s1[35], s2[35], t[35];cin >> s1 >> s2;int l1, l2, tl;l1 = strlen(s1);l2 = strlen(s2);bool hasSubstr = false;if(l1 < l2)//讓s1是較長的字符串，s2是較短的字符串 {//如果s1比s2短，那么二者交換 strcpy(t, s1);strcpy(s1, s2);strcpy(s2, t);l1 = strlen(s1);l2 = strlen(s2);}//l1>=l2的前提下，判斷l(xiāng)2是不是l1的子串 for(int i = 0; i < l1; ++i){//看l1從下標(biāo)i開始到(i+l2-1)%l1是不是與s2相同，如果相同則s2是s1的子串。要循環(huán)遍歷字符數(shù)組。 bool isSubStr = true;for(int j = 0; j < l2; ++j){if(s2[j] != s1[(i+j)%l1]){isSubStr = false;break;}}if(isSubStr){cout << "true";return 0;}}cout << "false";return 0; }

解法2：構(gòu)造新字符串并判斷子串

• 字符數(shù)組
  自己寫判斷子串函數(shù)

#include<bits/stdc++.h> using namespace std; 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[35], s2[35], t[35], c;cin >> s1 >> s2;int l1, l2, tl;l1 = strlen(s1);l2 = strlen(s2);if(l1 < l2)//讓s1是較長的字符串，s2是較短的字符串 {//如果s1比s2短，那么二者交換 strcpy(t, s1);strcpy(s1, s2);strcpy(s2, t);swap(l1, l2);}for(int i = 0; i < l1; ++i){if(isSubStr(s1, s2)){cout << "true";return 0;}//s1整體向左循環(huán)移位一格，s1[0]移動到最末尾 c = s1[0];for(int j = 0; j < l1 - 1; ++j)s1[j] = s1[j+1];s1[l1-1] = c;}cout << "false";return 0; }

使用strstr函數(shù)

#include<bits/stdc++.h> using namespace std; int main() {char s1[35], s2[35], t[35], c;cin >> s1 >> s2;int l1, l2, tl;l1 = strlen(s1);l2 = strlen(s2);if(l1 < l2)//讓s1是較長的字符串，s2是較短的字符串 {//如果s1比s2短，那么二者交換 strcpy(t, s1);strcpy(s1, s2);strcpy(s2, t);swap(l1, l2);}for(int i = 0; i < l1; ++i){if(strstr(s1, s2) != NULL)//判斷s2是否是s1的子串 {cout << "true";return 0;}//s1整體向左循環(huán)移位一格，s1[0]移動到最末尾 c = s1[0];for(int j = 0; j < l1 - 1; ++j)s1[j] = s1[j+1];s1[l1-1] = c;}cout << "false";return 0; }

• 使用string類
  自己寫判斷子串函數(shù)

#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())//讓s1是較長的字符串，s2是較短的字符串 swap(s1, s2);for(int i = 0; i < s1.length(); ++i){if(isSubStr(s1, s2))//判斷s2是否是s1的子串 {cout << "true";return 0;}//s1整體向左循環(huán)移位一格，s1[0]移動到最末尾 s1.push_back(s1[0]);//將第一個字符添加到末尾 s1.erase(s1.begin());//刪除第一個字符 }cout << "false";return 0; }

使用成員函數(shù)find

#include<bits/stdc++.h> using namespace std; int main() {string s1, s2;cin >> s1 >> s2;if(s1.length() < s2.length())//讓s1是較長的字符串，s2是較短的字符串 swap(s1, s2);for(int i = 0; i < s1.length(); ++i){if(s1.find(s2) != string::npos)//判斷s2是否是s1的子串 {cout << "true";return 0;}//s1整體向左循環(huán)移位一格，s1[0]移動到最末尾 s1.push_back(s1[0]);//將第一個字符添加到末尾 s1.erase(s1.begin());//刪除第一個字符 }cout << "false";return 0; }

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通 2050：【例5.20】字串包含 | OpenJudge NOI 1.17 19:字符串移位包含问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。