Explain how to modify knuth-morris-pratt algorithm

Assignment Help Data Structure & Algorithms

Reference no: EM1371025

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.

Reference no: EM1371025

Questions Cloud

Question about discount rate : Determine what would happen to GDP if a significant number of house spouses who were previously stay home to care for their children began taking jobs and placing their children in day care?

External environment and organization design : External Environment and Organization Design - how does the decision to enter an entirely new market affect the design decisions you as a manager make?

Explain how would constraints on financial resources vary : Explain how would constraints on financial resources vary with private pay, versus Medicare, charity or Medicaid pay as primary revenue streams for your facility.

Find out the magnitude of the electrostatic force : An air molecule is moving at a speed of 438m/s. How many meters would molecule move during 7ms (milliseconds) if it didn't collide with any other molecules.

Explain how to modify knuth-morris-pratt algorithm : Explain how to modify Knuth-Morris-Pratt algorithm to support patterns with these wild cards, and analyze modified algorithm. Your algorithm must find first substring in text which matches the pattern.

Overcome organization impediments to change : Impact of change - Show the impact of change. What methods can be applied to overcome organization impediments to change?

Illustrate what is elasticity of demand at profit maximizing : Illustrate what is elasticity of demand at profit maximizing level of output. Without use of any calculations, determine wherefirm=s total revenue would increase, decrease, or stay same if CRAPCO attempted to increase its price by .2%. Explain how..

Venture capital funding : Determine what are some of the sources companies can turn to for venture capital funding?

Question related to humanities : How did the more dynamic and complex view of the universe affect the literature, art, and composition of the early 20th century?

User Account

All Pages