西北工业大学ACM基地2022年大培训试题题解：第四周A题

描述

给定一个字符串S

对于每个询问，给出一个字符串T，问T是不是S的子串

（子串：连续的若干个元素）

输入

第一行输入一个字符串S

第二行输入一个正整数N，代表询问的个数

接下来的N行每行一个字符串T

1<=|S|<=500

1<=|T|<=|S|

1<=N<=100

S,T均由小写字母组成

输出

输出为N行

若T是S的子串，输出YES

输入样例

nwpunpuppu
3
npu
nn
pp

输出样例

YES
NO
YES

题解

思路

本题可用遍历方法。对每一个字符串，从总串开头开始遍历对应，检验是否是子串。

由于字符串长度不明，适用动态数组读取字符串。

源代码

// UOJ W4-A
#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    string sMain, sVice;
    int n = 0;
    bool flagS = 0;
    vector<char> sVMain, sVVice;
    cin >> sMain;
    for (auto i : sMain) //读取总字符串
    {
        sVMain.push_back(i);
    }
    cin >> n; //读取数字
    // cout << "Len of sVec:" << sVMain.size() << endl;
    while (cin >> sVice)
    {
        sVVice.clear(); //清空子动态数组
        // cout << sVice;
        for (auto i : sVice) //读取字符串
        {
            sVVice.push_back(i);
        }
        int nMain = (int)sVMain.size(); //动态数组维度是无符号整型，小心越界！
        int nVice = (int)sVVice.size();
        for (int i = 0; i <= nMain - nVice + 1 - 1; i++) //从sVMain
        {
            flagS = 1; //字符相同性标识
            for (int j = 0; j <= nVice - 1; j++)
            {
                if (sVVice[j] != sVMain[i + j]) //判断单个字符
                    flagS = 0;                  //不相同
            }
            if (flagS == 1) //存在子串就跳出
                break;
        }
        if (flagS == 1) //全部字符相同
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

=EOF=