Блог пользователя Hepic_Antony_Skarlatos

Multiple Queries/String Matching
Автор Hepic_Antony_Skarlatos, история, 10 лет назад, По-английски

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 !

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
10 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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)

→ Ответить
»
10 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +2 Проголосовать: не нравится

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.

→ Ответить
»
10 лет назад, скрыть # |
 
Проголосовать: нравится +25 Проголосовать: не нравится

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

→ Ответить