Finding the number of square prefixes of a string in linear time Let square denote a concatenation of two identical, nonempty
  strings. Given a string $w$, devise an $O(|w|)$
  algorithm that counts the number of prefixes of $w$ that are squares.


My initial idea was to use the prefix function $P$ from the Morris-Pratt algorithm ($P[i]$ is the length of the longest proper prefix of $w[1..i]$, being also its suffix), which can be calculated in linear time. Then, for each even index $i$ (we do not need to consider prefixes of odd length, as those obviously cannot be squares) the corresponding prefix $w[1..i]$ is a square if $P[i] = i/2$ and is not a square if $P[i] &lt; i/2$.

Now, the missing case which I am unsure how to handle is $P[i] &gt; i/2$. For example, let's consider the two strings: $abababab$ and $ababab$. The longest proper prefix-suffix of each of them is bigger than half the length of the string (6 and 4 correspondingly), yet the first one is a square and the second isn't.

Can anyone point me to an observation needed to resolve the missing part of the algorithm? Or is the idea to use the $P$ array wrong and a different approach should be applied to this problem?
Suppose there is an $O(|W|)$ algorithm that computes a slightly different prefix function: $Z[i]$ is the longest prefix of $W$ that is also a prefix of $W[i..n]$. Note then that your answer will simply be the count of indices $i$ such that $Z[i] &gt;= i$, assuming 0-indexing. 

Fortunately, such an algorithm exists and is quite elegant! It's (as always) a good idea to try to devise it on your own. If you get stuck, here's a pretty good explanation: http://codeforces.com/blog/entry/3107.