If there are $k$ disjoint matches for a prefix $p$, then the string can be divided such that $LCP = len(p)$. This can be done in linear time using KMP or the Z-algorithm. Performing binary search on the length of $p$ results in an $O(n \log n)$ solution.
We want an array $z$ such that $z[i]$ is the length of the longest prefix of $s$ matching the substring starting at $s[i]$. $z[0]$ is defined as 0.
If $s[1] = s[0]$ then $z[1] \geq 1$. If $s[2] = s[1]$ then $z[1] \geq 2$. Note that then also $s[2] = s[1] = s[0]$, so $z[1] = r - 1$ where $s = \underbrace{aa \dots aa}_rb$. ($r$ repetitions of the first character). For similar reasoning, $z[2] = r - 2$, $z[3] = r - 3$, etc.
But this is only for $z[1..r]$. How to compute $z[r..n)$? We use information of what we have already computed before.