Как рекурсивно сравнить векторы?

Question

Я пытаюсь написать функцию, которая рекурсивно проверяет, является ли данный вектор 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, потому что я не думаю, что моя логика правильная. Я не смог изменить его, чтобы дать какие-либо результаты. Любая помощь будет оценена!

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 линии так, что, когда я вызываю функцию в основном, он выдает либо истинным, либо ложным. Функция в настоящее время выводит значение 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

EDIT: V2 Теперь более эффективный поиск - начать поиск либо где последний поиск закончился или символ, который соответствует началу строки поиска

Вы также можете распечатать, где произошло первое совпадение, просмотрев savedPos - 1

Answer 2

Здесь вам нужны две рекурсивные функции, если вы хотите сделать все рекурсивно.

Один, чтобы проверить, найдена ли последовательность в определенной точке, и одна, чтобы использовать эту другую функцию для проверки равенства в каждой точке. Вот простая реализация шаблона, который будет работать с любым STL контейнер, который позволяет итерацию, а также не-STL последовательностей (таких как сырые массивы):

template <typename NeedleIterator, typename HaystackIterator = NeedleIterator> 
bool recursive_sequence_equals(
    NeedleIterator needle_begin, 
    NeedleIterator needle_end, 
    HaystackIterator haystack_begin, 
    HaystackIterator haystack_end) 
{ 
    // The sequences are equal because we reached the end of the needle. 
    if (needle_begin == needle_end) { 
     return true; 
    } 

    // If we reached the end of the haystack, or the current elements are not equal 
    // then the sequences are not equal here. 
    if (haystack_begin == haystack_end || *needle_begin != *haystack_begin) { 
     return false; 
    } 

    // We are not at the end of the haystack nor the needle, and the elements were 
    // equal. Move on to the next element. 
    return recursive_sequence_equals(
     ++needle_begin, needle_end, 
     ++haystack_begin, haystack_end); 
} 

template <typename NeedleIterator, typename HaystackIterator = NeedleIterator> 
HaystackIterator recursive_sequence_find(
    NeedleIterator needle_begin, 
    NeedleIterator needle_end, 
    HaystackIterator haystack_begin, 
    HaystackIterator haystack_end) 
{ 
    // We reached the end with no match. 
    if (haystack_begin == haystack_end) { 
     return haystack_begin; 
    } 

    // If the sequences are equal at this point, return the haystack iterator. 
    if (recursive_sequence_equals(needle_begin, needle_end, 
            haystack_begin, haystack_end)) { 
     return haystack_begin; 
    } 

    // Check the next position in the haystack. 
    return recursive_sequence_find(
     needle_begin, needle_end, 
     ++haystack_begin, haystack_end); 
} 

использовать так:

std::vector<int> a = { 5, 6, 7 }; 
std::vector<int> b = { 1, 2, 3, 4, 5, 6, 7 }; 

auto found = recursive_sequence_find(
    a.begin(), a.end(), 
    b.begin(), b.end()); 

if (found != b.end()) { 
    // There was a match, found is an iterator to the beginning of the match in b. 
} else { 
    // No match. (Or both containers were empty!) 
} 

(Demo)

---

Технически вы можете сделать это с помощью одной функции, если вы используете некоторые дополнительные параметры, чтобы передать whethe r или нет, вы находитесь в середине теста на равенство. Однако это добавляет много дополнительного усложнения для логики без усиления. Это проще и проще реализовать с использованием двух различных рекурсивных функций.

Answer 3

#include <stdio.h> 
#include <string.h> 
#include <vector> 
#include <iostream> 
using namespace std; 
bool r_app(vector<int> a, vector<int> b, int starta, int startb) 
{ 
    if(a.size() == 0) return 0; 
    if(starta == 0) { 
     int i=0; 
     while(1) { 
      while(a[0] != b[i] && i < b.size()) 
       i++; 
      if(i >= b.size()) return 0; 
      if(r_app(a, b, starta+1, i+1) == 1) 
       return 1; 
      else i++; 
     } 
    } 
    else { 
     if(starta == a.size()) 
      return 1; 
     else if(startb == b.size()) 
      return 0; 
     else if(a[starta] == b[startb]) 
      return r_app(a, b, starta+1, startb+1); 
     else 
      return 0; 
    } 
} 
int main() { 
    vector<int> a; 
    vector<int> b; 
    b.push_back(1); 
    b.push_back(2); 
    b.push_back(3); 
    b.push_back(4); 
    b.push_back(5); 
    a.push_back(3); 
    a.push_back(4); 
    cout << r_app(a,b,0,0); 
    return 0; 
} 

Будет проще, если вы не используете рекурсию. Кроме того, алгоритм KMP даст вам много оптимизированного решения.

Answer 4

Моя попытка, используя iterator:

#include <iostream> 
#include <vector> 
#include <algorithm> 

template<typename Iter> 
bool r_app(Iter first_a, Iter last_a, Iter first_b, Iter last_b) 
{ 
    if(first_a == last_a) //trivial case 
     return true; 

    auto found = std::find(first_b, last_b, *first_a); 
    if(found == last_b) 
     return false; 
    else 
     return r_app(++first_a, last_a, found, last_b); //recursion 
} 

int main() 
{ 
    std::vector<int> a{5,6,7}; 
    std::vector<int> b{1,2,3,4,5,6,7}; 
    std::cout << r_app(a.begin(),a.end(),b.begin(),b.end()); 

    return 0; 
}