Exact pattern matching problem

[Jenniferx]

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.

[eta oin shrdlu]

Is this homework? What have you tried so far? (Yes, you can do this with a convolution--well, actually a few convolutions.)

[Edited with clarification.]