Hepic_Antony_Skarlatos's blog

Multiple Queries/String Matching
By Hepic_Antony_Skarlatos, history, 10 years ago, In English

What is the most efficient algorithm when the problem gives you a string of N length and asks you to answer in Q queries if the ith word of length M (where M is much lesser than N -> M << N) is contained into 'N length word' ?

Thanks in advance !

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
10 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Well, if M is really small, you can compute hash for all possible words of size <= M inside the string N. Then, just compute the hash for the ith word and check if the same hash was found inside the string N.

Edit: this would be O(n*m + q*m)

→ Reply
»
10 years ago, hide # |
← Rev. 3  
Vote: I like it +2 Vote: I do not like it

You can compute the suffix array for the string of length N and then answer each query in O(M * logN), making the algorithm O(Q * M * logN). If M is small, it should run in time.

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

    I just know a MlogN algorithm. How I will get that in O(M) ?

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

      Yes, you're right. I fixed the typo. I'd need to know the actual constraints, but I guess this solution should be fast enough.

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

      I think you can get O(M) per query using suffix automaton.

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

        Yep. Just build a suffix automaton on the string of length N and after that for each query run a dfs from the start node of the automaton. If you can do all M transitions between the automaton states then the small string is contained in the big one. The time complexity is O(M)*O(Q)=O(M*Q).

        → Reply
»
10 years ago, hide # |
 
Vote: I like it +25 Vote: I do not like it

I think the most efficient algorithm for this kind of problems is Aho–Corasick

→ Reply