You are not logged in. Please login at www.codechef.com to post your questions!

×

How can we determine the number of occurrence of a substring using suffix automaton?

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?

asked 06 Aug '14, 14:26

tamimcsedu19's gravatar image

3★tamimcsedu19
3662711
accept rate: 0%

edited 06 Aug '14, 15:30

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×630
×5

question asked: 06 Aug '14, 14:26

question was seen: 1,577 times

last updated: 06 Aug '14, 15:30