K0NSTANT1N3's blog

String matching with universal characters in it
By K0NSTANT1N3, history, 11 months ago, In English

Given two strings: s1, s2 s1 has some characters that equal to every character (call them universal characters) and s1 also has some characters that are not equal to any character.

find all occurences of s1 in s2.

for example

s1 = ab?a? s2 = aabcabaaa

here s1 occurs in s2 on indexes 1 (as abcab) and 4 (as abaaa)

i have tried using KPM or Z Array, but both failed do to unpredictable misbihaviour.

what algorithm can be used to solve this problem in linear time? (or at least O(n*logn))?

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

»
11 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by K0NSTANT1N3 (previous revision, new revision, compare).

→ Reply
»
11 months ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

check https://codeforces.me/blog/entry/111380

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

I didn't find anything better than the algorithm with FFT here https://codeforces.me/blog/entry/111380. I think there might not be a better one since solving your problem kind of implies solving some convolution problem. Maybe you can solve it in O(something(m) + n) by using some algorithm, like a quadratic one or maybe the FFT to build the automata and then running it on the target string, although this wouldn't be useful in practice compared to just using the FFT algorithm unless the target string is very big for some reason.

→ Reply