Алгоритмы сопоставления с образцом [закрыто] ⇐ C++

[Anonymous]

Мне даны два вектора целых чисел, каждый из которых представляет собой вектор токенов из токенизированного кода, и меня просят сообщить общую длину (количество токенов) всех обнаруженных совпадений с шаблоном, длина которых составляет около 10–20. Более длинные совпадения с шаблоном будут считаться множественными совпадениями с шаблоном, но это не имеет значения, поскольку сообщается только общая длина.
Например,
arr1 = {1,2,3,4,5,6,7,8,9,10,23,34,234,34,23,12,14,16,18,20,22,24,26,28,30,32,34}
arr2 = {1,2,3,4,5,6,7,8,9,10,12,14,16,18,20,22,24,26,28,30,32,34,243,34,12}

Здесь первые 10 токенов совпадают, а следующие 12 токенов arr2 совпадают с последними 12 токенами arr1, поэтому алгоритм должен вернуть 22. Это это не LCS, потому что LCS насчитала бы 34 243, но это не так. Можно ли это решить за O(n) или, может быть, за O(nlogn)?
Мне удалось придумать только наивный подход к этой задаче, который требует O(10×10× n×m) время или можно сказать O(n×m). Я только что проверил каждую последовательность длиной 10-20, чтобы найти совпадения. Он не был полностью точным, но давал почти правильные результаты. Вот что я сделал,
int match_submissions(std::vector &arr1, std::vector &arr2) {
if (arr1.empty() || arr2.empty()) {
return 0;
}

int result = 0;

int m = arr1.size();
int n = arr2.size();

std::unordered_sets;

for(int size=20; size>=10; size--){
for(int i=0; i

Подробнее здесь: https://stackoverflow.com/questions/791 ... algorithms