Many String matching applications allow the following wild card characters in the pattern

1. The wild card ? represents arbitrary single character. For example the pattern s?r?ng matches the string,sprung and sarong.

2. The wild character * represents an arbitrary string of zero or more characters. For example the pattern te*s*t matches test, tensest.

Both wild characters can occur in single pattern. For example f*a?? matches the string face, football. On the other hand neither wild card can occur in the text.

Describe how to modify the Knuth-Morris-Pratt algorithm to support patterns with these wild cards, and analyze the modified algorithm.Your algorithm should find the first substring in the text that matches the pattern.