Repeated Substring Pattern

Instead of proving that the function returns false when the string is not of the specified form, let us use the contraposition.

Let $s = a_1…a_n$ be the string and assume that the function returns true. That means that $s$ is a substring of $a_2a_3…a_na_1a_2…a_{n-1}$. Since $s$ is of length $n$, that means that there exists $k\in\{2, …, n\}$ such that: $$s = a_ka_{k+1}…a_na_1…a_{k-1}$$

Let $u = a_k…a_n$ and $v = a_1…a_{k-1}$. Then neither $u$ nor $v$ is empty and $s = uv = vu$.

Suppose (without loss of generality) that $|u| \leqslant |v|$ and let us prove by induction on $|u| + |v|$ that there exists $w$ and $m_1$, $m_2$ such that $u=w^{m_1}$ and $v = w^{m_2}$:

• if $|u| + |v| = 2$, then $u$ and $v$ are one-letter words and the result is direct with $w = u$ and $m_1 = m_2 = 1$;

• otherwise, since $uv = vu$ and $|u| \leqslant |v|$, that means that $u$ is a prefix of $v$, and there exists $v'$ such that $v = uv'$.

  • If $v' = \varepsilon$, then $w = u$ and $m_1 = m_2 = 1$ are suitable.
  • Otherwise $uuv' = uv'u$, so $uv' = v'u$. Using induction hypothesis, there exists $w$ and $m_1$ and $m_2'$ such that $u = w^{m_1}$ and $v' = w^{m_2'}$. Then $v = uv' = w^{m_1+m_2'}$.

Since $s = uv$, then $s = w^{m_1+m_2}$, and $w$ is a proper substring of $s$, because $m_1 +m_2 > 1$.