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