When I have build a suffix automaton for string T(suppose T=“ababcab”), then if I want to know how many times a sub-string occurs in (i.e how many times Pattern P = “ab” occurs in T), how can I do that?

EDIT: I have found an implementation like this:

let cnt[v] is the For all the states v number of occurrence of the substrings associated with v.

Initially if state v was not cloned then cnt[v] = 1 , otherwise it’s 0. We go through each state in descending order of length. and for each state we do cnt[link[v]]+=cnt[v]; After that , if u is the state corresponding to pattern P , then cnt[u] is the ans.

But I can’t really understand why this works?

1 Like