Exact string matching problem

Page 1 of 1

1 Replies - 1336 Views - Last Post: 23 October 2011 - 12:20 PM

Topic Sponsor:

#1 JennifferX  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 23-October 11

Exact string matching problem

Posted 23 October 2011 - 12:37 AM

This is my homework and I am not looking for someone to do it for me. I just need some suggestions to move forward, because I've been thinking on it for a while and I am stucked. Any suggestions will be appreciated.

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

Is This A Good Question/Topic? 0
  • +

Replies To: Exact string matching problem

#2 KYA  Icon User is offline

  • #include <beer.h>
  • member icon

Reputation: 2544
  • View blog
  • Posts: 18,732
  • Joined: 14-September 07

Re: Exact string matching problem

Posted 23 October 2011 - 12:20 PM

Start here

Posting the code you have with specific questions regarding implementation is the way to go.
Was This Post Helpful? 0
  • +
  • -
Page 1 of 1