[数据结构与算法]信息学奥赛一本通 2050：【例5.20】字串包含

【题目链接】

ybt 2050：【例5.20】字串包含

【题目考点】

1. 字符串

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

字符串模式匹配有多种算法，如：KMP、BM、Sunday、Horspool等等，如想学习，可以自行搜索。
本文只给出最基本的枚举法，来判断一个字符串是不是另一个字符串的子串。

• 字符数组

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. 查找子串函数

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 ：循环遍历并比较

先确定输入的两个字符串哪个更长哪个更短，设更长的为s1，更短的为s2。其中s1的长度为l1，s2的长度为l2。判断s2是否可以是s1的子串。
尝试从s1的每个位置出发，循环遍历向后数l2个字符（如果到末尾，就回到第0位置继续数），看这l2个字符和s2是否相同。如果存在相同的情况，那么s1位移包含s2，输出true。如果不存在相同的情况，输出false。

解法2： 构造新字符串并判断子串

先让s1是较长的字符串，s2是较短的字符串。s1长度l1，s2长度l2。
让s1做l1次循环移位（每个字符向左移位一次，第0个字符移位到最后），每次得到一个新字符串s1，判断s2是否是这个新的s1的子串。判断一个字符串是否是另一个字符串的子串，参考【题目考点】3、4，可以用自己写的函数，也可以用c++库中存在函数。

【题解代码】

解法1：循环遍历并比较

#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的前提下，判断l2是不是l1的子串 
    for(int i = 0; i < l1; ++i)
    {//看l1从下标i开始到(i+l2-1)%l1是不是与s2相同，如果相同则s2是s1的子串。要循环遍历字符数组。 
        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：构造新字符串并判断子串

• 字符数组
  自己写判断子串函数

#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整体向左循环移位一格，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函数

#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整体向左循环移位一格，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类
  自己写判断子串函数

#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整体向左循环移位一格，s1[0]移动到最末尾 
        s1.push_back(s1[0]);//将第一个字符添加到末尾 
        s1.erase(s1.begin());//删除第一个字符 
    }
    cout << "false";
    return 0; 
}

使用成员函数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整体向左循环移位一格，s1[0]移动到最末尾 
        s1.push_back(s1[0]);//将第一个字符添加到末尾 
        s1.erase(s1.begin());//删除第一个字符 
    }
    cout << "false";
    return 0; 
}