4

I need to detect a cycle/sequence in a string and return the first occurrence. How should I go about doing it?

Example :

2 0 5 3 1 5 3 1 5 3 1

The first sequence to occur is 5 3 1.

There is no rules. The sequence can be half the string length, for example 

5 3123 1231 231 31 231 41 452 3453 21 312312 5 3123 1231 231 31 231 41 452 3453 21 312312

The sequence is 5 3123 1231 231 31 231 41 452 3453 21 312312

Mat
  • 202,337
  • 40
  • 393
  • 406
seesee
  • 1,145
  • 5
  • 20
  • 46
  • 5
    No, it is actually `1 2 5`. Is there a minimal length for the cycle, or the number of repeats? By "cycle" do you mean that the repeated occurrences must be consecutive? – Péter Török Apr 21 '12 at 07:27
  • yes is 1 2 5... I tried cycling all the char and etc. – seesee Apr 21 '12 at 07:31
  • 2
    Need more information. Is there a minimum length for such a sequence? Does it count if the occurrences of the sequence aren't next to each other in the string ( so, for 3 1 2 5 7 1 2 5 ... , does 1 2 5 count)? And if the answer to the last question is yes, should we consider the first occurrence of the sequence or the second occurrence of the sequence when deciding which comes first? (So for 1 2 3 4 5 6 4 5 6 1 2 3, is the first repeated sequence 1 2 3 or 4 5 6)? You need to start thinking about these things before you (or anyone else) can come up with a solution. – Dawood ibn Kareem Apr 21 '12 at 07:33
  • 2
    As @pst noted, it is appreciated if you make a honest effort trying to solve the problem first, then tell us what have you tried, how far you got, and what concrete problem you bumped into. And it is *not* appreciated if you just try to coax us into doing your homework for free. If you haven't bothered to even try, why should we? – Péter Török Apr 21 '12 at 07:33
  • there is no minimal length.. yes cycle means repeated occurrences must be consecutive. – seesee Apr 21 '12 at 07:33
  • @Peter Torok - well the entire assignment is 100 marks.. I already completed 90 marks.. just want to get 10 marks.. i tried loop the entire array from the start and etc. – seesee Apr 21 '12 at 07:35
  • This question is similar - http://stackoverflow.com/questions/88615/what-algorithm-can-you-use-to-find-duplicate-phrases-in-a-string – pidge Apr 21 '12 at 07:36
  • 1
    @user1342688, if you show us your code, we will be happy to help improving / fixing it. – Péter Török Apr 21 '12 at 07:37
  • 8
    @user1342688 - if you don't do the work yourself, you don't DESERVE those extra marks. Seriously, why do you THINK they award marks for homework? It is to get YOU to do it!! – Stephen C Apr 21 '12 at 07:38
  • Here is [a similar enough problem, with several different solutions](http://stackoverflow.com/questions/3675390/how-to-find-repeating-sequence-of-characters-in-given-array) you can adapt to your case. – Péter Török Apr 21 '12 at 07:50
  • Why isn't the first one just `1 2`? – user unknown Apr 21 '12 at 09:34
  • hmm I think I should rephrase the question.. – seesee Apr 21 '12 at 09:40
  • The first repeated sequence is `5` – Bohemian Apr 21 '12 at 10:57

2 Answers2

7

Have you studied Floyds cycle-finding algorithm? That may well help you if you want to find cycles. Very easy to implement as well.

rossum
  • 15,344
  • 1
  • 24
  • 38
3

Clarification based on the comments: cycle means a sequence of digits which repeats immediately. So 

1 1

would be a cycle

1 3 1

wouldn't because the potential cycle of 1s is interupted by 3

1 3 1 3

is a cycle (1 3).

So a basic algorithm could look like this.

  1. Iterate of the String.

  2. For each Digit find it next occurrence in the String. If nothing found continue with the next character.

  3. If a next occurrence is found compare the sequence from the current digit up to the following occurrence with the sequence of same length beginning at the next occurence. If they are the same you found a cycle. If not continue with the next occurence.

Jens Schauder
  • 77,657
  • 34
  • 181
  • 348