Periodic String

Periodic String

Google Interview String

Find out if a given string is periodic.
e.g.
Given "abababab"
return true

Given "ababa"
return false

Given "abcdabcd"
return true

Solution

A shortcut for this problem:
Given a string S,
create a new String T by removing the first and last characters of (S + S).
If S is a substring of T, then S is periodic.

Prove

Assume S is a periodic string that consists of N repeated sections R.
(If S = "xyzxyz", then N = 2 and R = "xyz")

Known
S = N * R
T = (S + S without first and last chars), in other words the first R and last R are broken.
Hence, T = S + S - 2R = N * R + N * R - 2R = (2N - 2) * R

In order for S to be a substring of T, T has to be greater or equal to S
T >= S , replace T and S by N and R.
(2N - 2) * R >= N * R, eliminate R on both sides
2N - 2 >= N, solve the formula
N >= 2
In other words, in order for S to be a substring of T, the repetition N >= 2.
Therefore, S = N * R >= 2 * R, which implies that the pattern R repeats over twice in S.

At this point the only thing left to look at is whether S is a substring of T.
This can be done efficiently by KMP algorithm in O(n) time.
For a tutorial on KMP, click here KMP Algorithm.

Implementation

boolean isPeriodic(String s) {
    StringBuilder str = new StringBuilder(s + s);
    str.deleteCharAt(0);
    str.deleteCharAt(str.length() - 1);
    return strStr(str.toString(), s);
    //click here for implementation of KMP strStr()
}