PROBLEM LINK:
Author: Learner Club
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
PROBLEM:
In short problem was to find the minimum length substring, whose repetition generates the entire input string.
EXPLANATION:
Method O(n):
Lets take an example to understand the problem more clearly. Suppose the input string is “abcabcab” and you need to find the minimum length string whose repetition generates the entire input string. So the possible repetition for the given input string could be “abcabc” or “abc” or “bca” or “cab” or “bcabca”.
If we write “abcabc” as 2 times then we can generate “abcabcab” as its substring.
Similarly input string can be generated as a substring with the repetition of “abc” 3 times, “cab” 3 times and so on.
Since the question is to find the length of the smallest string whose repetition generates the entire string. Therefore the answer is 3 because of any of the following three strings “cab”, “bca” or “abc” of length 3. Hence the answer is 3.
The brute force solution of finding all possible substrings will give TLE because of large constraint.
You need to be familiar with the new concept of prefix function used in KMP string matching algorithm.
So the prefix function of the string is the length of the longest proper suffix which is also the prefix of the string. Proper suffix is the substrings of the original string and it does not include the original string.
Lets take an example
For “aaaa” String the value of prefix function is 3 because the longest proper suffix is “aaa”. Lets take another example, for “ababab” the longest proper suffix is “abab”.
Coming back to our original problem.
So the answer will be prefix value of input string subtracted from the length of Input string.
Lets see how this statement justifies our sample example taken earlier.
In previous case our input string was “abcabcab”
which is of length 8 and the answer which we
computed was 3.
Now lets compute the value of prefix
function for the given input string.
So the longest proper suffix which is also the
prefix is “abcab” and it’s length is 5.
Now subtracting the lengtho f prefix
function from the length of input string
gives 3, which matches with our result.