找到这题的出处了。还没看太懂。
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.
