c++ - 如何递归比较 vector ？

Question

我正在尝试编写一个函数，它递归地检查给定 vector A 是否在 vector B 中的任何连续 block 中。例如，如果 A={5,6,7} 和 B={1,2,3,4,5,6,7}，它应该返回真。如果 B = {1,2,3,4,5,7,6}，它应该返回 false。目前，我的代码一直输出 true 因为我认为我的逻辑不正确。我还不能修改它来产生任何结果。任何帮助将不胜感激!

bool r_app(vector<int>& a1, vector<int> b1, size_t k)
{
    k=0;

    if (a1.size() == 0) {
        cout << "true";
        return true;;
    }

    for (int i=0;i<a1.size();i++){
        for(int j=0;j<b1.size();j++){  
            if (a1.at(i)==b1.at(j)) {
                cout << "true" << endl;
                return true;
            }   
        }
        cout << "false" << endl;
        return false;    

        return r_app(a1,b1,k+1);   
    }
}

编辑: 这就是我从 Smac89 得到的，我添加了 cout 行，这样当我调用 main 中的函数时，它会输出 true 或 false。该函数当前为每个真输入输出真，但不输出假。我不确定为什么。

bool r_app(std::vector<int>& a1, std::vector<int> &b1, std::size_t start)
{
    std::size_t savedPos = start + 1, k = 0;

    for (; k < a1.size() && start < b1.size() && a1[k] == b1[start]; 
         k++, start++)
    {
            if (k != 0 && a1[0] == b1[start])
                savedPos = start;
    }
    if (k == a1.size())
        cout << "true" << endl;
        return true;
    if (start < b1.size())
        return r_app(a1, b1, savedPos);

    cout << "false" << endl;  
    return false;
}

Answer 1

template <typename T>
bool r_app(std::vector<T>& a1, std::vector<T> &b1, std::size_t start) {
    std::size_t savedPos = start + 1, k = 0;

    for (; k < a1.size() && start < b1.size() && a1[k] == b1[start]; 
         k++, start++)
    {
            if (k != 0 && a1[0] == b1[start])
                savedPos = start;
    }
    if (k == a1.size())
        return true;
    if (start < b1.size())
        return r_app(a1, b1, savedPos);

    return false;
}

template <typename T>
bool r_app(std::vector<T>& a1, std::vector<T>& b1) {
    return r_app(a1, b1, 0);
}

例子: http://rextester.com/COR69755

编辑: V2 现在更高效的搜索 - 在上次搜索结束的地方或与搜索字符串开头匹配的字符处开始搜索

您还可以通过查看 savedPos - 1

打印出第一次匹配发生的位置