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

For example, in "12345123451234512345", what开发者_如何学JAVA is an efficient algorithm to find "12345"?

Coding in C++.

Thanks.

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.