Hi,
I am trying to solve this specific example, 32.4-4 from Cormen page
930:
+++++++++++++++++++++
Show how to improve KMP-Matcher by replacing the occurrence of π in
line 7 (but not line
12) by π', where π' is defned recursively for q = 1, 2, ..., m-1 by
the equation
{ 0 if π [q] = 0;
π' = { π'[π [q]] if π [q] != 0 and P[π [q] + 1] = P[q + 1];
{ π [q] if π [q] != 0 and P[π [q] + 1] != P[q +
1];
Explain why the modifed algorithm is correct, and explain in what
sense this modification constitutes an improvement.
+++++++++++++++++++++
I understand that at line 7 of the algorithm (see below), instead of
finding the value in the pre-computed table of π[q] and assigning q
to be whatever π[q] is during the while loop, we instead assign π'[q].
π'[q] is defined recursively in terms of π[q]. From what I can tell it
enumerates the values of π*[q] for you, instead of needing to iterate
through them with the while loop.
I just don't understand why this is an improvement. Is it because it
requires fewer iterations of the while loop? if so, wouldn't the cost
be the same, because the recurrence has to make the same
comparisons...
Can someone please help?
Thanks
NOTE Here is the code for KMP-Matcher:
KMP-MATCHER(T, P)
1 n ← length[T]
2 m ← length[P]
3 π ← COMPUTE-PREFIX-FUNCTION(P)
4 q ← 0 //Number of
characters matched.
5 for i ← 1 to n //Scan the
text from left to right.
6 do while q > 0 and P[q + 1] ≠ T[i]
7 do q ← π[q] //Next
character does not match.
8 if P[q + 1] = T[i]
9 then q ← q + 1 //Next character
matches.
10 if q = m ?Is all of P matched?
11 then print "Pattern occurs with shift" i - m
12 q ← π[q] //Look for the
next match.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
