0
$\begingroup$

A proper prefix of a string $s$ that is also equal to a suffix of $s$ is called a PS (prefix-suffix).

Given a string $s$ of length $n$ is there an algorithm listing the lengths of all the PSs in $O(n^{1+\epsilon})$ time?

KMP can find the longest PS in linear time. Then we can note that the second longest PS is the longest PS of the longest PS so we can apply KMP iteratively but that is $O(n^2)$ in the worst case (e.g. if $s=aaaa\dots a$).

$\endgroup$
1
$\begingroup$

Simply note that KMP is incremental: it finds the longest PS (also known as border) for every prefix of the string. If you don't throw away that information, you don't need to re-run KMP for every prefix.

$\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.