Wildcard Matching Queries?

Revision en2, by i_love_sqrt_decomp, 2025-06-25 11:26:20

I want to ask this problem: There are $$$Q$$$ queries and 2 strings $$$S,T$$$ of length $$$N$$$, each containing $$$l_1,l_2,r_1,r_2$$$, which asks for wildcard matching on the substrings $$$S[l_1...r_1]$$$ and $$$T[l_2...r_2]$$$ (Assume $$$r_1-l_1=r_2-l_2$$$). Can it be done faster than $$$O(NQ)$$$?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English i_love_sqrt_decomp 2025-06-25 11:26:20 17 Tiny change: ' wildcard pattern matching ' -> ' wildcard matching '
en1 English i_love_sqrt_decomp 2025-06-25 06:07:12 311 Initial revision (published)