1

I have a vector that is filled dynamically and will always contain a repeating sequence with characters and length that I am unsure of. For example, the vector could contain these elements:

0 1 1 2 3 1 0 1 1 2 3 1 0 1 1 2

and the repeating sequence in that vector is:

0 1 1 2 3 1

How can I search the vector and find those elements. I would like to put the found sequence in a new vector. I assumed at first it would only take a simple for loop and checking for repetition of the first and second element in the array, so in the case above I would exit the loop when I reached 0 1 a second time, but the problem is that it cannot be assumed that the first 2 elements will be in the repeating pattern, so

0 1 2 3 2 3 2 3 2 3

can be valid elements in the vector. Any ideas?

frontin
  • 733
  • 2
  • 12
  • 28
  • Perhaps refer to this: http://stackoverflow.com/questions/10355103/finding-the-longest-repeated-substring – Michael Albers Oct 03 '15 at 23:59
  • http://stackoverflow.com/questions/11090289/find-longest-repetitive-sequence-in-a-string. This problem is equivalent of finding largest pattern with a little tweak. In finding longest pattern, algo discards the last found pattern if it is smaller to the newly found pattern, but in your case you may want to keep it if the new longer pattern does not overlap with older pattern. – Ritesh Oct 03 '15 at 23:59
  • You want the *longest* repeating sequence, yes? – Beta Oct 04 '15 at 00:00
  • @Beta yes that is correct – frontin Oct 04 '15 at 00:04

1 Answers1

0

in general (infinite result) it is impossible to know the sequence because something like that can happen 1 million 0 and then 1,after 1000 zero u will think that the sequence is zero only,but if the vector is finite you can write somethink like that 

for(I..VECTORSIZE / 2)
if(VECTORSIZE  % I == 0)
 CHECK IF SUBVECTOR(0,I) == SUBVECTOR(I,I*2) == SUBVECTOR(I*2,I*3)....
    return I
else continute;
ido kahana
  • 165
  • 2
  • 8