k790alex's blog

[HELP] LA 4670 — Dominating Patterns
By k790alex, 10 years ago, In English

Hi, since sometime ago, I was trying to solve this problem.

I tried using brute force, suffix array and suffix tree, and I got TLE.

My approach is this:

  • Create a suffix tree for the text O(M)

  • Count how many times appear each pattern in the text O(N*S)

  • Find the answer O(N)

where:

M = text length

N = number of patterns

S = pattern length

Can some give me any hints?

Thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Try Aho-Corasick algorithm.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Finally I got it using AC, thanks.

    What an interesting algorithm!

    Now, I have a question, I read this paper: Efficient String Matching: An Aid to Bibliographic Search.

    In page 6 it talk about "Eliminating failure transitions" or "Algorithm 4" to get a better runtime, I tested not using function and got a better runtime without this function.

    Do you have some idea?

    Is really best to use this function?

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

      Well, this function can make moving to the next state O(1) worst-case while without this function it would be O(1) amortized but O(n) worst-case. But then construction of automaton will be O(nΣ) instead of O(n). Well, it can be useful when the trie of patterns pretty small and the text is really big. Also it can be useful when we want to sometimes erase symbols from the end of text. With this function we can do it in O(1) worst-case while without it there could be some data that makes AC runs in O(n2)

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

        Thanks, I did't know about last application.

        I ran the same codes in UVA and using algorithm 4 got better runtime.

        → Reply