When I have build a suffix automaton for string T(suppose T="ababcab"), then if I want to know how many times a substring 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? asked 06 Aug '14, 14:26
