This website uses cookies to ensure you have the best experience.

# Knuth Morris Pratt Algorithm Essay

2243 words - 9 pages

PKnuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm
Kranthi Kumar Mandumula

December 18, 2011

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

outline

Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

Deﬁnition History Components of KMP Algorithm Example Run-Time Analysis Advantages and Disadvantages References

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Deﬁnition:

Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

Best known for linear time for exact matching. Compares from left to right. Shifts more than one position. Preprocessing approach of Pattern to avoid trivial comparisions. Avoids recomputing ...view middle of the document...

It enables avoiding backtracking on the string ‘S’.

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

m ← length[p] a[1] ← 0 k ←0 for q ← 2 to m do while k > 0 and p[k + 1] k ← a[k ] end while if p[k + 1] = p[q] then k ←k +1 end if a[q] ← k end for return Here a =

Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

p[q] do

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Computation of Preﬁx-function with example: Knuth-Morris-Pratt
Algorithm Kranthi Kumar Mandumula

Let us consider an example of how to compute for the pattern ‘p’. Pattern a b a b a c a

I n i t i a l l y : m = length [ p]= 7 [1]= 0 k=0 where m, [1], and k are the length of the pattern, preﬁx function and initial potential value respectively.

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Knuth-Morris-Pratt Algorithm

Step 1 : q = 2 , k = 0 [2]= 0 q p 1 a 0 2 b 0 3 a 4 b 5 a 6 c 7 a

Kranthi Kumar Mandumula

Step 2 : q = 3 , k = 0 [3]= 1 q p 1 a 0 2 b 0 3 a 1 4 b 5 a 6 c 7 a

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Knuth-Morris-Pratt Algorithm

Step 3 : q = 4 , k = 1 [4]= 2 q p 1 a 0 2 b 0 3 a 1 4 b 2 5 a 6 c 7 a

Kranthi Kumar Mandumula

Step 4 : q = 5 , k = 2 [5]= 3 q p 1 a 0 2 b 0 3 a 1 4 b 2 5 a 3 6 c 7 a

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Knuth-Morris-Pratt Algorithm

Step 5 : q = 6 , k = 3 [6]= 1 q p 1 a 0 2 b 0 3 a 1 4 b 2 5 a 3 6 c 1 7 a

Kranthi Kumar Mandumula

Step 6 : q = 7 , k = 1 [7]= 1 q p 1 a 0 2 b 0 3 a 1 4 b 2 5 a 3 6 c 1 7 a 1

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

A f t e r i t e r a t i n g 6 times , t h e p r e f i x f u n c t i o n computations i s complete : q p 1 a 0 2 b 0 3 A 1 4 b 2 5 a 3 6 c 1 7 a 1

The running time of the preﬁx function is O(m).

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Algorithm

Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

Step 1 : I n i t i a l i z e t h e i n p u t v a r i a b l e s : n = Length o f t h e Text . m = Length o f t h e P a t t e r n . = Prefix −f u n c t i o n of pattern ( p ) . q = Number o f c h a r a c t e r s matched . Step 2 : D e f i n e t h e v a r i a b l e : q=0 , t h e b e g i n n i n g o f t h e match . Step 3 : Compare t h e f i r s t c h a r a c t e r o f t h e p a t t e r n w i t h f i r s t c h a r a c t e r o f text . I f match i s n o t found , s u b s t i t u t e t h e v a l u e o f [ q ] to q . I f match i s found , then i n c r e m e n t t h e v a l u e o f q by 1 . Step 4 : Check whether a l l t h e p a t t e r n elements are matched w i t h t h e t e x t elements . I f not , r e p e a t t h e search process . I f yes , p r i n t t h e number o f s h i f t s taken by t h e p a t t e r n . Step 5 : l o o k f o r t h e n e x t match .

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

n ← length[S] m ← length[p] a ← Compute Preﬁx function q←0 for i ←...

## Other assignments on Knuth Morris Pratt Algorithm

### Course Syllabus Essay

2610 words - 11 pages [pic] COURSE SYLLABUS Semester: Fall, Year: 2012  College Mission Statement Richard J. Daley College provides high-quality education which leads to academic success, career development, and personal enrichment that fulfill diverse community needs. Mathematics Department Mission Statement Our mission is to deliver excellent service and to provide learning opportunities by offering a wide range of mathematics courses, which will help our

### Management Essay

1477 words - 6 pages Boeing Management Planning Heather Oetzel MGT 330 October 22, 2012 Joe Cheng Abstract Boeing is known as “the world’s leading aerospace company and the largest manufacturer of commercial jetliner and military aircraft combined ("The Boeing Company: About Us", 2012). Every company uses different types of management techniques including how the planning function of management is used. Planning allows organizations to develop how the

### Assisted Suicide

1015 words - 5 pages Should physician-assisted suicide be legal? While I believe if one chooses to end his or own life through physician assistance for reasons that they chose, the choice should be up to the individual. Physician-assisted suicide should be at one's discretion. “Assisted Suicide, also called Voluntary Euthanasia, is currently a contentious issue in many countries. Because Euthanasia is legal in a few modern democracies: the Netherlands, Belgium

### Tanglewood Case 1

797 words - 4 pages Tanglewood’s staffing strategy requires the organization to make key decisions about the acquisition, deployment, and retention of the organization’s workforce. In order to accomplish this, Tanglewood’s must make thirteen decisions regarding its staffing levels and its staffing quality. One of the first decisions that Tanglewood needs to choose is to acquire or develop talent. Tanglewood should try to develop their current talent because one

### Nnnnn

1391 words - 6 pages Есе по въпроса: Кои от всички „действащи” лица могат да се разглеждат като морално отговорни и в какво именно? по казуса Форд „Пинто” Корпоративните злодеяния са нанесли повече вреди на обществото от всички улични престъпления взети заедно. Според данни на ФБР сумата от уличните престъпления възлиза на \$3.8 млрд. годишно, а загубите от корпоративните измами между \$100 млрд. и \$400 млрд. годишно

### The Penis

1052 words - 5 pages The short story ”The Penis” is written by Hanif Kureishi. The short story is about a penis, which has been separated from its owner Doug, who we hear from later on. At first though we hear about a guy called Alfie who was “a cutter – a hairdresser – and had to get to work”. He is having breakfast with his wife, when she asks him what he did last night, and if he had a good time last night? Alfie can not remember what he did last night, he then

### Managed Care Paper

543 words - 3 pages Managed Care and Case Management Care Marvin Lloyd BSHS/402-Case Management 27 August 2012 Virgil Miller Managed Care are techniques employed to help reduce the cost for providing health benefits and a system for improving organizations quality of care

### Media

439 words - 2 pages The life expectancy is lower; so people are not kept alive with drugs for decades in a virtual sleep state. There is less state education; so kids don't have it drilled into them that their only goal in life is to make money, at the cost of 'everything' else. The health care is less; so diseases, usually brought by Westerners, kill many more than they do in countries where drug companies can make a fortune from selling medicines that aren't

7113 words - 29 pages CGGGG The Political Economy of International Trade Chapter Outline OPENING CASE: Why Are Global Food Prices Soaring? INTRODUCTION INSTRUMENTS OF TRADE POLICY Tariffs Subsides Country Focus: Subsidized Wheat Production in Japan Import Quotas and Voluntary Export Restraints Local Content Requirements Administrative Polices Antidumping Policies Management Focus: U.S. Magnesium

### Scope And Goals

279 words - 2 pages Introduction: Kudler Fine Foods is a specialty food store based in San Diego, California with its three locations in La Jolla, Del Mar, and Encinitas. Kudler Fine food prides itself on offering fresh and organic products that are carefully selected from local farmers and around the world. The organization has recently taken the initiative to start a Frequent Shopper Program to market and increase sales. This program will offer the customers a

### Meerkat

251 words - 2 pages Meerkat The meerkat or suricate, Suricata suricatta, is a small mammal belonging to the mongoose family. Meerkats live in all parts of theKalahari Desert in Botswana, in much of the Namib Desert in Namibia and southwestern Angola, and in South Africa. A group of meerkats is called a "mob", "gang" or "clan". A meerkat clan often contains about 20 meerkats, but some super-families have 50 or more members. In captivity, meerkats have an average

## Similar Documents

### Mgt216 Essay

714 words - 3 pages The first ethical issue presented in the ethics game simulation was whether to warn consumers about the contaminated product and what information to provide consumers about the contaminant. The second ethical issue was whether to sell a product that does not meet U.S. safety requirements in a foreign market that has lower safety restrictions. G-BioSport was not required to meet prior approval from the Federal Drug Administration before they

### Economy Effect Of Marijuana Essay

277 words - 2 pages Modern American History by Alan Renga 2nd Mid Term! You will be given 3 Short Essay questions and 20 Multiple Choice questions deriving from this list! 80 points total! The 1920s Warren Harding then Calvin Coolidge Tea Pot Dome 1st Red Scare Immigration Restriction, Sacco and Vanzetti Langston Hughes, Marcus Garvey, KKK Prosperity, advertising Prohibition, Al Capone Flappers, Clara Bow, Rudolph Valentino Babe Ruth, Jack Dempsey

### The Vc Shakeout Essay

2033 words - 9 pages ECONOMY 26 Luring a big ﬁrm to town is not the secret to job growth DEFEND YOUR RESEARCH 30 Are morning people wired for success? VISION STATEMENT 32 The social web’s east-west divide COLUMN 38 Warren Bennis looks back on his surprising path to fame New Thinking, Research in Progress hbr.org New Thinking, Research in Progress hbr.org FIRST The VC Shakeout Venture capital hasn’t worked for a decade and must be radically

### Hospitals Paper

6014 words - 25 pages I hope to provide in this paper a comprehensive understanding for what the term “hospital” has become. Hospitals are an extremely complex system that man has created and shaped and reshaped throughout history. My goal in writing and researching this paper will be to provide those who read it a clear understanding on how the hospital system got to where it is today, and to shed some light on the many organizations that affiliate with and