String Matching with Wildcard | Algorithms Notes

String Matching with Wildcard | Algorithms Notes

Given two strings T and P with wildcards, where |T| = n and |P| = m, design an algorithm to find a substring of T that matches P. Solution: Naive approach will take O(nm) time. Suppose that we map all letters in the alphabet to positive integers and we treat the wildcard as zero. Then, for each start position i in T, we can compute and this value is zero if, and only if there is a match starting at i. We can evaluate all values in O(n lg n) time by using FFT. If we partition T into n/m overlapping substring of length 2m, then all values can be evaluated in O(n lg m) time. Like this: Like Loading... This entry was posted in Interview Question . Bookmark the permalink . Enter your comment here... Fill in your details below or click an icon to log in: Email (required) (Address never made public) Name (required) You are commenting using your WordPress.com account. (  Log Out  /  Change  ) You are commenting using your Twitter account.

Read full article from String Matching with Wildcard | Algorithms Notes