raihatneloy's blog

Help in 291E — Tree-string problem
By raihatneloy, 9 years ago, In English

Can this problem be solved using Suffix Automaton? I want to know if we can solve this using this algorithm. Can anyone please share any ideas? Thanks in advance :)

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Actually it's a problem on KMP algorithm...

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have already solved using KMP & DFS. But i want to know if it has any idea on SAM.

    → Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

You don't even need suffix automata, I think you can do it in O(N) just with tree DFS and kmp :)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have already solved using KMP & DFS. But i want to know if it has any idea on SAM.

    → Reply