Scribd Logo
Upload

Welcome to Scribd!

  • 91 views

    KMP String Matching Algorithm

    Uploaded by

    Shrinath Tailor
    The document describes the Knuth-Morris-Pratt (KMP) string matching algorithm. It shows an example of applying the KMP algorithm to match a pattern string to a main string. It demonstrates how the algorithm shifts the pattern by one position if a mismatch occurs, and uses a prefix table to determine how many positions to shift the pattern by. The document also explains how to construct the prefix table and use it to efficiently shift the pattern during matching.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    KMP String Matching Algorithm

    Uploaded by

    Shrinath Tailor
    91 views8 pages
    The document describes the Knuth-Morris-Pratt (KMP) string matching algorithm. It shows an example of applying the KMP algorithm to match a pattern string to a main string. It demonstrates how the algorithm shifts the pattern by one position if a mismatch occurs, and uses a prefix table to determine how many positions to shift the pattern by. The document also explains how to construct the prefix table and use it to efficiently shift the pattern during matching.

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes the Knuth-Morris-Pratt (KMP) string matching algorithm. It shows an example of applying the KMP algorithm to match a pattern string to a main string. It demonstrates how the algorithm shifts the pattern by one position if a mismatch occurs, and uses a prefix table to determine how many positions to shift the pattern by. The document also explains how to construct the prefix table and use it to efficiently shift the pattern during matching.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    91 views8 pages

    KMP String Matching Algorithm

    Uploaded by

    Shrinath Tailor
    The document describes the Knuth-Morris-Pratt (KMP) string matching algorithm. It shows an example of applying the KMP algorithm to match a pattern string to a main string. It demonstrates how the algorithm shifts the pattern by one position if a mismatch occurs, and uses a prefix table to determine how many positions to shift the pattern by. The document also explains how to construct the prefix table and use it to efficiently shift the pattern during matching.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 8

    String Matching Algorithm - KMP

    String a b c d e f g h String a b c d e f g h
    Pattern d e f Pattern d e f
    Not Match, Shift by one Not Match, Shift by one

    String a b c d e f g h String a b c d e f g h
    Pattern d e f Pattern d e f
    Not Match, Shift by one Match, Compare Next

    String a b c d e f g h String a b c d e f g h
    Pattern d e f Pattern d e f
    Not Match, Shift by one Match, Shift by one

    Shrinath Tailor, SBCET - Jaipur


    String Matching Algorithm - KMP

    String a b c d e f g h
    Pattern d e f
    Pattern Matched, Return the position

    Next example

    Shrinath Tailor, SBCET - Jaipur


    String Matching Algorithm - KMP
    i
    String: a b c d a b c a b c d f If character at i and j position matched, mover both i and j to next position
    Pattern a b c d f
    j

    i
    String: a b c d a b c a b c d f
    Pattern a b c d f
    j
    If character at i and j position Not matched,
    move j to 1st of position of Pattern and count the total no of character move
    i back by j
    String: a b c d a b c a b c d f
    Now move back i to the total no of character counted by j and move next by 1.
    Pattern a b c d f do the same process.
    j
    i
    String: a b c d a b c a b c d f
    Here Count = 4
    Pattern a b c d f
    j

    Shrinath Tailor, SBCET - Jaipur


    String Matching Algorithm - KMP
    i i
    String: a b c d a b c a b c d f String: a b c d a b c a b c d f
    Pattern a b c d f Not Matched Pattern a b c d f Matched
    j j

    i
    String: a b c d a b c a b c d f i
    Pattern a b c d f Not Matched String: a b c d a b c a b c d f

    j Pattern a b c d f Matched
    j

    i i
    String: a b c d a b c a b c d f String: a b c d a b c a b c d f
    Pattern a b c d f Not Matched Pattern a b c d f Matched
    j j

    Shrinath Tailor, SBCET - Jaipur


    String Matching Algorithm - KMP
    i
    String: a b c d a b c a b c d f
    Pattern a b c d f Not Matched
    j

    Here count = 3

    i
    String: a b c d a b c a b c d f
    Pattern a b c d f
    j

    Shrinath Tailor, SBCET - Jaipur


    String Matching Algorithm - KMP
    Creating Π Table (Longest Prefix matched with suffix.

    a b c d a b e a b f
    0 0 0 0 1 2 0 1 2 0

    a a b c a d a a b e
    0 1 0 0 1 0 1 2 0 0

    a b c d e a b f a b c
    0 0 0 0 0 1 2 0 1 2 3

    Shrinath Tailor, SBCET - Jaipur


    String Matching Algorithm - KMP
    S[1] == p[1] Matched ; i++, j++

    S[2] == p[2] Matched; i++, j++


    String i
    a b a b c a b c a b a b a b d
    j S[3] == p[3] Matched; i++, j++
    0 1 2 3 4 5
    Pattern a b a b d
    S[4] == p[4] Matched; i++, j++
    Π Table 0 0 1 2 0
    S[5] == p[5] Not Matched; j = 2

    i
    Compare s[i] with p[j+1]
    a b a b c a b c a b a b a b d
    If match – increase i and j by 1 j
    0 1 2 3 4 5
    Else if not matched a b a b d
    Pattern
    Move back j to their Π table value
    if table value is 0 than increase i by 1 Π Table 0 0 1 2 0

    Shrinath Tailor, SBCET - Jaipur


    String Matching Algorithm - KMP
    i
    S[5] == p[5] Not Matched; j = 2
    a b a b c a b c a b a b a b d
    i j
    a b a b c a b c a b a b a b d 0 1 2 3 4 5
    j Pattern a b a b d
    0 1 2 3 4 5 Π Table 0 0 1 2 0
    Pattern a b a b d

    Π Table 0 0 1 2 0 S[5] == p[1] Not Matched; j = 0


    Here j = 0 so we cannot move back j so increase the value of i by 1;
    i
    S[5] == p[3] Not Matched; j = 0 a b a b c a b c a b a b a b d
    j
    0 1 2 3 4 5
    Pattern a b a b d

    Π Table 0 0 1 2 0

    Shrinath Tailor, SBCET - Jaipur

    You might also like