Question

如何判断一个字符串中是否包含另一个字符串

Answer 1

包含有两种意思：

1. 字符串t是字符串s的字串（t的每个字符在s中顺序排列，但不一定连续），例如"srt"被包含于"ehiseriutey"

2. 字符串s的某段与字符串t相等（t的每个字符在s中顺序排列，且连续），例如"skir"被包含于"hskskirtnn"

对于第一种，用贪心算法，即按照字符串s的每一位枚举，匹配t中的第i位（i从0开始），便继续在s中匹配t的下一位，直到将t找完（即s包含t），如果到了s的最后一位，t仍没有被匹配完，那么s不包含t。

代码如下：

// 第一种情况 
#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char s[100],t[100];
    
    cin>>s;
    cin>>t;
    
    int slen = strlen(s) , tlen = strlen(t); // 获取s和t的长度
    int i = 0;
    bool flag = false; // 标识字符串t是否被匹配完全
    
    for(int j=0 ; j<slen ; j++) // 枚举s的每一位
    {
        if(s[j] == t[i]) // 如果s的第j位和t的第i位相同，继续在s中匹配t[i+1]
            i++;  // 继续在s中匹配t[i+1]
        if(i==tlen)  如果t的所有位都在s中被匹配
        {
            flag = true; // 返回"t被包含于s"
            break; // 跳出循环，节省时间
        }
    }
    // 如果此时t没有被完全匹配（i<n）,则flag保持false。
    
    if(flag)
        cout<<"t被包含于s"<<endl;
    else
        cout<<"t不被包含于s"<<endl;
    
    return 0;
}

以上是第一种情况的代码。

对于第二种，仍可以用贪心，设t的长度为tlen，则判断s中以每一位开始的长度为tlen的字串是否等于t，如果等于，则输出是，如果s的每一位都不满足要求，则输出否。

代码如下：

// 第二种情况 
#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char s[100],t[100];
    
    cin>>s;
    cin>>t;
    
    int slen = strlen(s) , tlen = strlen(t); // 获取s和t的长度
    bool flag = false; // 标识字符串t是否被匹配完全
    char tmp[tlen]; //用来临时存储s[i]到s[i+tlen-1]组成的字符串，便于和t比较
    
    for(int i=0 ; i<slen-tlen ; i++) // 枚举s的每一位,如果到了大于slen-tlen的长度，则剩余长度小于tlen，不可能匹配出t
    {
        for(int j=i;j<i+tlen;j++) // 将以s[i]开头的tlen位字符串复制到tmp里 
            tmp[j-i]=s[j];
            
        if(strcmp(tmp,t) == 0) // 如果和t匹配
        {
            flag = true;
            break;
        }
    }
    
    if(flag)
        cout<<"t被包含于s"<<endl;
    else
        cout<<"t不被包含于s"<<endl;
    
    return 0;
}

另外，还有一种更强大的kmp算法，将每一位枚举变成了直接跳转到可能匹配的字符，可以自行搜索。