An easy problem. We just need to take each substring $s_{sub}$ of the given string $s$ in increasing length order and check if it matches the constraints. What are the constraints?

  • Length of $s_{sub}$ divides evenly into length of $s$. Let, $\ddfrac{s.\textrm{length}}{s_{sub}.length} = q$.
  • When $s_{sub}$ is concatenated $q$ times, it matches with $s$.

Given the above two constraints, here’s the implementation in C++:

Worst case time complexity is $\mathcal{O}(n^2)$, where $n$ is the input size. This happens when the smallest period is the input string length.