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
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
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
Название |
---|
Why you can't create one if construction, like:
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 stringa?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.
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://mirror.codeforces.com/problemset/problem/754/E and http://mirror.codeforces.com/blog/entry/49613?#comment-335977
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).
Here it is (I uploaded it some time ago) https://pl.spoj.com/problems/AL_09_09/ . You can test your solution. The statement is in polish, but it simply asks you to count the number of pattern matches.
Same story — wanted to solve in linear time what passed in quadratic — https://leetcode.com/problems/wildcard-matching/. Btw, care to share your linear solution?