Какой алгоритм использовать для получения соответствия самой длинной строки в двух больших массивах?

Проблему легко объяснить: у нас есть два больших массива (32-битные целые числа), и мы должны найти все общие последовательности выше заданного количества последовательных позиций (n) .

Например, если n = 3 и массивы для сравнения:

a = [1, 3, 5, 7, 3, 2, 7, 4, 6, 7, 2, 1, 0, 4, 6]
b = [2, 5, 7, 3, 2, 3, 4, 5, 6, 3, 2, 7, 4, 6, 0]

Алгоритм должен вернуть два массива:

r0 = [5, 7, 3, 2]
r1 = [3, 2, 7, 4, 6]

(или, лучше, его относительные позиции относительно первого массива и количество последовательных совпавших байтов).

Я считаю, что неплохо для начала - это Алгоритм самой длинной общей подстроки , но, возможно, кто-нибудь знает алгоритм, который лучше или точно соответствует моей проблеме.

8
задан Ivan 17 July 2011 в 13:25
поделиться