You are not logged in. Please login at www.codechef.com to post your questions!

×

Help with KMP algorithm!!!

I have an issue with precomputation algorithm in KMP algorithm... I was reading it from Geeksforgeeks and I have a problem in understanding that else part Why do we do len=lps[len-1]?? When we do dont find the last character matching we shorten up the suffix too(I visualise the len as the length of longest suffix and longest prefix matching)!! And if we do len=lps[len-1] then i think we are simpply ignoring the second last character???

       else // (pat[i] != pat[len])
   {
     if (len != 0)
     {
       // This is tricky. Consider the example AAACAAAA and i = 7.
       len = lps[len-1];

       // Also, note that we do not increment i here
     }
     else // if (len == 0)
     {
       lps[i] = 0;
       i++;
     }
   }

asked 23 Mar '15, 18:53

anh1l1ator's gravatar image

6★anh1l1ator
142618
accept rate: 11%

edited 23 Mar '15, 19:00


a) We calculate lps because in case of mismatch we didn't have to start over again.

b) In case pat[] = AAACAAAA and i=7; len=3 and it mismatches [A!=C]; if we see the lps[len]=0; it will not be fruitful.

But lps[len-1] = lps[2]= A ;

it makes lps=[0,1,2,0,1,2,3,3] .

It is due to lps[l-1] we can have two 3 at last.

link

answered 24 Mar '15, 00:59

global_worker's gravatar image

2★global_worker
11
accept rate: 0%

edited 24 Mar '15, 01:02

We aren't ignoring anything, because we have valid computed lps values for previous positions already. Try to look at it in following way - we have some string, we want to add new char and compute length of longest matching between prefix and suffix. You try largest possible matching from old string, and check that added char matches with corresponding char in prefix. If it does - OK; otherwise you have to take some shorter prefix-suffix match; your old string looks like AxA, where A and x are some strings (it is also possible that there are no x at all, and two entrances of A overlap, but it does not matter here). You want to try some smaller preffix-suffix match. But if you will take some shorter suffix - it will be also a suffix of A, not only a suffix of original AxA string. And of course all shorter prefixes of AxA are also prefixes of A. Therefore your moved from solving question for AxA to solving question for A now; and this move is done by line len=lps[len-1].

link

answered 24 Mar '15, 00:02

lebron's gravatar image

7★lebron
3.3k317
accept rate: 24%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,664
×643
×86
×75

question asked: 23 Mar '15, 18:53

question was seen: 2,728 times

last updated: 24 Mar '15, 01:02