Hello everyone ,

I am trying to read this top coder tutorial and understood the working of KMP algorithm completely.

I have found this problem at the end of this post.

A typical problem seen quite often is: given a string find its shortest substring, such that the concatenation of one or more copies of it results in the original string. Again the problem can be reduced to the properties of the failure function. Let’s consider the string

A B A B A B

and all its proper suffix/prefixes in descending order:

1 A B A B
2 A B
3 /the empty string/

Every such suffix/prefix uniquely defines a string, which after being “inserted” in front of the given suffix/prefix gives the initial string. In our case:

1 A B
2 A B A B
3 A B A B A B

Every such “augmenting” string is a potential “candidate” for a string, the concatenation of several copies of which results in the initial string. This follows from the fact that it is not only a prefix of the initial string but also a prefix of the suffix/prefix it “augments”. But that means that now the suffix/prefix contains at least two copies of the “augmenting” string as a prefix (since it’s also a prefix of the initial string) and so on. Of course if the suffix/prefix under question is long enough. In other words, the length of a successful “candidate” must divide with no remainder the length of the initial string.

So all we have to do in order to solve the given problem is to iterate through all proper suffixes/prefixes of the initial string in descending order. This is just what the “failure function” is designed for. We iterate until we find an “augmenting” string of the desired length (its length divides with no remainder the length of the initial string) or get to the empty string, in which case the “augmenting” string that meets the above requirement will be the initial string itself.

This is what i have understood from the solution : use KMP failure function and find each suffix/prefix of the initial string and then for each of the suffix/prefix p that satisfies the |s|%|p| == 0. construct the string and check it against the given string. If you find any valid string (choose the best one) otherwise the answer is original string itself. Am i right ?? Can anybody explain it in a better way or can someone provide me link to the above problem. I think i have understood the idea wrongly otherwise same thing can also be done each prefix of the initial string once (i know that time complexity of this will be O(N^2)). what will be the time complexity of the solution described in the post ? Please help