Find the smallest period of input string in O(n)?

问题:

Given the following problem :

Definition :

Let S be a string over alphabet Σ .S' is the smallest period of S if S' is the smallest string such that :

S = (S')^k (S'') ,

where S'' is a prefix of S. If no such S' exists , then S is not periodic .

Example : S = abcabcabcabca. Then abcabc is a period since S = abcabc abcabc a, but the smallest period is abc since S = abc abc abc abc a.

Give an algorithm to find the smallest period of input string S or declare that S is not periodic.

Hint : You can do that in O(n) ...

My solution : We use KMP , which runs in O(n) .

By the definition of the problem , S = (S')^k (S'') , then I think that if we create an automata for the shortest period , and find a way to find that shortest period , then I'm done.

The problem is where to put the FAIL arrow of the automata ...

Any ideas would be greatly appreciated ,

Regards

回答1:

I'm not sure that I understand your attempted solution. KMP is a useful subroutine, though -- the smallest period is how far KMP moves the needle string (i.e., S) after a complete match.

回答2:

this problem can be solved using the Z function , this tutorial can help you .

回答3:

See if this solution works for O(n). I used rotation of strings.

public static int stringPeriod(String s){

    String s1= s;
    String s2= s1;

    for (int i=1; i <s1.length();i++){
        s2=rotate(s2);
        if(s1.equals(s2)){
            return i;
        }
    }

    return -1;
}

public static String rotate(String s1){

    String  rotS= s1;

    rotS = s1.substring(1)+s1.substring(0,1);

    return rotS;

}

The complete program is available in this github repository