Can you please help with solving the following problem. Given a string $s$, we need to find the number of borders of all its substrings. For a single string we can count all the borders in O(n) time using z-algorithm, but for the problem mentioned above this is obviously not an optimal approach. How can we solve this optimally perhaps by using a suffix array and LCP? Thank you!

A border of a string $s$ is a substring $t$ such that $s \neq t$ and $t$ is simultaneously a prefix of $s$ and a suffix of $s$.

Example: s = "abacaba".

Here the substrings "a", "aba" are the borders of $s$.

  • $\begingroup$ Please define "borders". What are your thoughts? What is the best algorithm you have been able to find so far? What is the context where you encountered this task? Can you credit the original source? You might find this page helpful in improving your question. $\endgroup$
    – D.W.
    Aug 17 at 17:44

Your Answer

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

Browse other questions tagged or ask your own question.