2025年信息学奥赛一本通 1140：验证子串 - OpenJudge NOI 1.7 18

大家好，我是讯享网，很高兴认识大家。

【题目链接】

【题目考点】

1. 字符串处理

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

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; else cout << "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; else cout << "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"; else cout << 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"; else cout << s2 << " is substring of " << s1; return 0; }

2025年信息学奥赛一本通 1140：验证子串 - OpenJudge NOI 1.7 18

【题目链接】

【题目考点】

1. 字符串处理

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

3. 查找子串函数

【解题思路】

解法1：枚举判断子串

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

【题解代码】

解法1：枚举判断子串

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

相关推荐