Assume that we have a # symbol that matches any symbol (including itself). For example, if T = ab#aca#ab#a and P = da#ac then P occurs starting at position 3 in T.
How to find a O(n log n) time algorithm for determining whether a pattern P of length n occurs in a text T of length 2n, assuming that the # symbol
occurs (possibly O(n) times) in T and P?
I think we can solve this problem using convolution/FFT but not sure how.
Any ideas are appreciated.