CODEWITHSUNDEEP
c++arraysalgorithm
anonymous
anonymous

Reputation: 1968

Find all repeating subsequence in array

I am not proficient in algorithm design but was asked this question in one of the job interview. My solution was naive one with heavy complexity but can this be done in shorter time.

Given an array of integers find all the sub sequence of that array which repeats in array. Print sub sequence and then start index and end end index of all their occurrence.

e.g 1,0,1,9,5,1,9,5,1

Here it should print 

1,9,5

3:5 6:8

9,5,1

4:6 7:9

1,9

3:4 6:7

5,1

5:6 8:9

9,5

4:5 7:8

My solution was to start from Arr[0] till Arr[N/2 -1] and check if it repeats then do reduced end index by 1 and keep on checking if it repeats.

Thanks

Upvotes: 3

Views: 1345

Answers (1)

real
real

Reputation: 491

I think you're talking about contiguous subarrays, instead of subsequences that are not necessarily contiguous. Your solution is O(n^3). You can use a suffix tree, which allows you to find the repeating subarray in O(n).

http://www.geeksforgeeks.org/suffix-tree-application-3-longest-repeated-substring/

Upvotes: 3

Related Questions