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
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
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
Name |
---|
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?