# 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] < i/2$.

Now, the missing case which I am unsure how to handle is $P[i] > 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?

• Have you tried using a suffix tree? (reversed) – Yuval Filmus Feb 19 '16 at 19:33
• Difference between $|w|$ and $P[|w|]$ and divisibility? – greybeard Feb 20 '16 at 0:13

## 2 Answers

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] >= 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.

• An in-depth description of the Z-Algorithm (Z-Algorithm/Z-Map is famous among competitive programmers but I don't know if it's the real name): youtube.com/watch?v=MFK0WYeVEag. – mrk Feb 20 '16 at 15:13
• I think I have come across the notion of the Z array (under a different name actually) when reading about possible approaches to computing the shift table in the Boyer-Moore algorithm. Either way, the linked article helped me a lot to understand how to construct it. Thanks! – Quintofron Feb 24 '16 at 3:35

It's also easy to do with a Rabin-Karp-type hash: https://en.wikipedia.org/wiki/Rolling_hash, which you can use to check equality of any two substrings in $O(1)$ time, albeit with a probability of error. This probability can be made negligible and works very well in practice.

I prefer the above-suggested "Z-Algorithm" solution because it's deterministic, but more so because it's a cool algorithm that is not well-known.