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

KMP with question marks?
Автор zed_b, история, 5 лет назад, По-английски

Hello, does anybody know if I can modify KMP for a pattern string with '?' symbols, that match any single character, so that I can find whether a pattern P that may contain '?' is in a text T (without '?') in O(|T|) time? Cheers

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

»
5 лет назад, # |
  Проголосовать: нравится -33 Проголосовать: не нравится

Why you can't create one if construction, like:

 while(j != 0 && (s[j] != '?' && s[i] != s[j])
→ Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 4   Проголосовать: нравится +125 Проголосовать: не нравится

    Because algorithms are not just a random code. It is much more about proofs. In case of KMP we use transitivity of the equality, when iterating over the borders.

    If j is a border of S[1..i] and h is a border of S[1..j], then h is a border of S[1..i]

    And with the wildcards equality is not transitive: $$$a= ?$$$, $$$?= b$$$, $$$a\neq b$$$. So with the naive algorithm after appending b to string a?ab we will get $$$p(5)=2$$$ ($$$p(p(4))=1$$$, $$$b=?$$$)

    There are efficient algorithms based on FFT (works in O(|T| log)) for the pattern matching with wildcards.

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

I don't know something very related to KMP that works, but this problem can be solved with bitsets in $$$O(|P|*|T|/32)$$$ (bruteforce complexity but $$$1/32$$$ constant) with bitsets, or in $$$O((|P|+|T|)*log(|P|+|T|))$$$ using FFT. To see how, check the editorial of http://codeforces.net/problemset/problem/754/E and http://codeforces.net/blog/entry/49613?#comment-335977

→ Ответить
»
5 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Do you have a link for this problem ?

A year ago I implemented that (in linear time) for buscando-palabras (the constraints allow quadratic solutions but I wanted to challenge myself with a linear solution).

→ Ответить