Search code examples
c++visual-studio-2008stringfindcycle

An efficient algorithm and code to find cycle in a string in C++?

For example, in "12345123451234512345", what is an efficient algorithm to find "12345"?

Coding in C++.

Thanks.

Solution

  • Going on your single example:

    12345123451234512345 returns 12345

    I think what you want is to find the longest possible needle that is repeated to complete the haystack, i.e. 1212121212 => 12, 444 => 4 and so on.

    The simplest solution would be to pick the first character and run through the string comparing for matches. If at any point you have a mismatch, pick the first two characters and run through the entire string comparing and so on, until your window size becomes greater than half the string.

    Complexity should be O(n^2)

    You can optimize which window size you pick based on the length of the string, i.e. the window sizes can only be divisors of the length of the string.