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

We need to prove two things:
1, if S is not a substring in T, then S is not a periodic string:
If S is not a substring in T, then there doesn't exist a section R, where R is the prefix in the string S remove R. That means S is not a periodic string.

2, if S is a substring in T, then S is a periodic string:
If there are more than one matches of S in T, then we pick the first match from i to j.
We have S in T between T[i] to T[j]. That's S = T.substring(i, j).
We define the middle point as m.
We know i < m < j, because T is created by removing the first and last characters of (S + S).
Then we know
T.substring(i, m) = S.substring(0, m-i)
T.substring(m+1, j) = S.substring(m-i+1, j-i)
Here we can assume j - m > m - i (vice versa can also prove)
Then we know S.substring(0, m-i) is the prefix of S.substring(m-i+1, j-i), because T.substring(m+1, j) is from the middle point to the right, which is the start point of S.
We define string R = S.substring(0, m-i).
Because S.substring(0, m-i) is the prefix of S.substring(m-i+1, j-i), we know S.substring(m-i+1, j-i) also has prefix R. Then we know S has prefix RR, R.concat(R)
Keep doing this, we have S with the prefix of NR, which is R repeat maximum N times.
Let's define S = NR concat another String Q
Here we know Q is a suffix of S, also Q is shorter than R.
Because Q ends at the middle point m. We also know Q is a prefix of S.
Let's define R = Q concat another string W
W is the prefix of S, then W is the prefix of R, then we know (W concat Q) = R
Then we know T.substring(i - W.length, j - W.length) also matches S
Then T.substring(i, j) is not the first match of S in T. (remember we pick the first match S in T as i to j)
Then there is a contradiction if Q.length > 0.
So we know Q.length=0. And S = NR.

Implementation

This can be done efficiently by KMP algorithm in O(n) time.
For a tutorial on KMP, click here KMP Algorithm.

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()
}