## Exact pattern matching problem

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Larson, Moderators General, Prelates

### Exact pattern matching problem

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.
Jenniferx

Posts: 1
Joined: Sun Oct 23, 2011 7:25 am UTC

### Re: Exact pattern matching problem

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.]

eta oin shrdlu

Posts: 408
Joined: Sat Jan 19, 2008 4:25 am UTC