如何递归地比较向量？ [英] How to recursively compare vectors?

问题描述

我想写一个函数，递归检查给定向量A是否在向量B中的任何连续块中。例如，如果 A = {5,6,7} 和 B = {1,2,3,4,5,6,7} ，它应该返回true。如果 B = {1,2,3,4,5,7,6} ，它应该返回 false 。目前，我的代码继续输出 true ，因为我不认为我的逻辑是正确的。我还没有能够修改它以产生任何结果。

I'm trying to write a function which recursively checks if a given vector A is in any contiguous block in vector B. For example, if A={5,6,7} and B={1,2,3,4,5,6,7}, it should return true. If B = {1,2,3,4,5,7,6}, it should return false. Currently, my code keeps outputting true because I don't think my logic is correct. I have not been able to modify it to produce any results yet. Any help will be appreciated!

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);   
    }
}

EDIT：是我从Smac89得到的，我添加了cout线，以便当我调用main中的函数，它输出true或false。该函数目前输出true的每个真正的输入，但不输出假..我不知道为什么。

So this is what I got from Smac89, and I added the cout lines so that when I call the function in main, it outputs either true or false. The function currently outputs true for every true input, but doesnt output false.. I'm not sure why.

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;
}

推荐答案

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
现在更高效的搜索 - 从上次搜索结束或与搜索开头匹配的字符开始搜索字符串

V2 Now more efficient searching - start a search either where the last search ended or at a character that matches the start of the search string

您还可以通过查看 savedPos - 1

这篇关于如何递归地比较向量？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！