Find all repeating subsequence in array

Question

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

Are you talking about contiguous or non-contiguous subsequences? Should they be adjacent to each other or not? 1 is repeated several times in your sample array, but is absent in your sample output (it is definitely sub-sequence and it is repeated). — n0rd
– n0rd, Commented Jun 15, 2015 at 19:34

real · Accepted Answer · 2015-06-15 19:05:21Z

3

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/

answered Jun 15, 2015 at 19:05

real

4915 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Ankur Over a year ago

Substring and subsequence is completely different.OP is asking about printing subsequence.

j_random_hacker Over a year ago

@Shan: "subsequence" is indeed the word the OP uses, but based on the example s/he gives, s/he means "substring".

Anderson Green Over a year ago

To find repeating (possibly non-contiguous) subsequences, I would use an algorithm like PrefixSpan.

Collectives™ on Stack Overflow

Find all repeating subsequence in array

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related