CODEWITHSUNDEEP
algorithmsearchpseudocode
NxA
NxA

Reputation: 159

Find same sequences of values in arrays

I have N different arrays with different numbers of elements. I want know if there is a good algorithm to find same sequences of values.

For example:

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

I want, as result, that all the three arrays have the sequence 5,6,7 in common. Any suggestion?

Upvotes: 2

Views: 304

Answers (1)

Ahmad Faiyaz
Ahmad Faiyaz

Reputation: 326

You can use Suffix Array and LCP or Suffix Trie to solve this problem. Check this tutorial : http://wcipeg.com/wiki/Longest_common_substring

It will work in O(NLogN) time, where N is summation of all the sequence's length.

if number of list is not big then you can use dynamic programming solution explained here: http://wcipeg.com/wiki/Longest_common_substring#Dynamic_programming_solution

Upvotes: 1

Related Questions