How to find the Longest Common Subarray of m arrays each of size n?

user_13417270 0
Viewed 3170

We have a 2D matrix A of M rows where each row is filled with a permutation of natural numbers from 1 to N (A[M][N])

We have to determine the length of the longest common Subarray among all the rows of the matrix

Example :

A = {{1,2,3,4},{3,4,1,2},{3,1,2,4}}

Longest common Subarray {1,2}

Length of LCS = 2

Output = 2

I don't need the code just a suggestion for optimization.

array-algorithms data-structures c algorithm
1 Answers

1)Iterate through each array, let i-th array be A[i]
2)Go through each subarray of A[i] calculating their hashes and putting them with the
length of subarray into map<pair<hashType, int>, int> counting how many times hash appeared
3)find the hash that appeared n times with the maximum length
if you have any questions on this comment below

user_155715600
Related