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