У меня есть N разных массивов с разным количеством элементов. Я хочу знать, есть ли хороший алгоритм для поиска одинаковых последовательностей значений.
Например:
a= 1,2,3,4,5,6,7,8
b= 9,10,13,5,6,7,13,12
c= 20,36,24,11,2,3,5,6,7,9,11
В результате я хочу, чтобы все три массива имели общую последовательность 5,6,7. Любое предложение?
Для решения этой проблемы вы можете использовать Suffix Array и LCP или Suffix Trie. Проверьте это руководство: http://wcipeg.com/wiki/Longest_common_substring
Он будет работать за время O (NLogN), где N - это сумма всей длины последовательности.
если количество списков невелико, вы можете использовать решение для динамического программирования, описанное здесь: http://wcipeg.com/wiki/Longest_common_substring#Dynamic_programming_solution
