1
$\begingroup$

I am trying to use the suffix array, and the LCP array to count all distinct substrings of a specified length.

I started with the algorithm for counting ALL distinct substrings. I solved it after this explanation: https://www.geeksforgeeks.org/count-distinct-substrings-string-using-suffix-array/ . The problem right now is that I can't figure out how to only count the substrings of my given length, and not all possibilities.

I also computed the array which tells me how many suffixes are lexicographically smaller than suffix_array[i].

Any ideas what I could use to do it?

$\endgroup$
0
$\begingroup$

The geeksforgeeks solution gives an efficient algorithm that accomplishes the following:

  • Sorts the suffixes of the input string in lexicographic order.
  • For every two adjacent suffixes in this order, finds the longest common prefix.

If you are after the number of distinct substrings of length $\ell$, you should proceed as follows:

  • If the first suffix has length at least $\ell$, initialize your counter with 1, otherwise with 0.
  • Now go over all the suffixes in lexicographic order. If the new suffix has length at least $\ell$ and the lcp with the preceding suffix has length smaller than $\ell$, then increment the counter.

For example, suppose that the string is ababa, and you're after substrings of length $\ell = 3$. The ordered suffixes are a, aba, ababa, ba, baba. The algorithm proceeds as follows:

  • The first suffix a is shorter than $\ell$, so the counter starts at 0.
  • The second suffix aba has length at least $\ell$, and the lcp with the preceding suffix has length less than $\ell$, so increment the counter. (We have discovered aba.)
  • The third suffix ababa has length at least $\ell$, but the lcp with the preceding suffix also has length at least $\ell$.
  • The fourth suffix ba has length less than $\ell$.
  • The fifth suffix baba has length at least $\ell$, and the lcp with the preceding suffix has length less than $\ell$, so increment the counter. (We have discovered bab.)
$\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.