5381: C++实验：STL之search -526互联

描述

使用STL中的search函数，判断一个序列是否是另一个序列的子序列。

部分代码已经给出，请补充完整，提交时请勿包含已经给出的代码。

int main()
{
    vector<int> vec1, vec2;
    int n, m, a;
    cin>>n>>m;
    while(n--)
    {
        cin>>a;
        vec1.push_back(a);
    }
    while(m--)
    {
        cin>>a;
        vec2.push_back(a);
    }
    Check(vec1, vec2);
    return 0;
}

输入

第一行为一个正整数n和m，n和m为元素个数（n<=1000）。

第二行有n个整数，表示序列1的所有元素。

第三行有m个整数，表示序列2的所有元素。

输出

如果序列2是序列1的子序列，则输出所在子序列的始末位置。

否则输出None。

样例输入

5 2
1 3 2 4 5
3 2

样例输出

2 3

定义一个Check函数，使用std::search函数来查找vec2在vec1中的位置。std::search函数返回一个迭代器，指向在vec1中找到的vec2的第一个元素的位置。如果vec2不是vec1的子序列，std::search函数将返回vec1.end()。

以下是完整的代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3+10,inf = 0x3f3f3f3f;
void Check(vector<int>& vec1, vector<int>& vec2)
{
    vector<int>::iterator it;
    it = search(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());
    if(it != vec1.end())
    {
        cout << distance(vec1.begin(), it) + 1 << " " << distance(vec1.begin(), it) + vec2.size() << endl;
    }
    else
    {
        cout << "None" << endl;
    }
}
int main()
{
    vector<int> vec1, vec2;
    int n, m, a;
    cin>>n>>m;
    while(n--)
    {
        cin>>a;
        vec1.push_back(a);
    }
    while(m--)
    {
        cin>>a;
        vec2.push_back(a);
    }
    Check(vec1, vec2);
    return 0;
}

在这个代码中，distance(vec1.begin(), it) + 1计算的是vec2在vec1中的开始位置，distance(vec1.begin(), it) + vec2.size()计算的是vec2在vec1中的结束位置。注意，这里的位置是从1开始计数的，所以我们需要加1。