5
$\begingroup$

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?

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – mrk Feb 20 '16 at 15:13
  • $\begingroup$ 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! $\endgroup$ – Quintofron Feb 24 '16 at 3:35
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.