Knuth Morris Pratt String Searching

I found some free time in the midst of extensive preparations ( for the end of semester examinations, I managed to salvage some time to write some Python code (I’ve written so much Java that Python now equals a rub on the temples).

Search:

A parallel comparision is made on the text to be searched and the keyword. That is, we go character by character and check if the ith character in the keyword equals the ith character in the text for i: 0 -> len(keyword). If we encounter a failure in our check, we restart from a particular point in the string which is determined by a table of values which tell us how far we need to backtrack to get the values.

So here is the search algorithm:

#!/usr/bin/env python
#Author: Shriphani Palakodety
#Mail: shriphani@shriphani.com
#Mail2: spalakod@purdue.edu

import make_table

def search(text, key):
        m = 0 #beginning of match in text
        i = 0 #position of the character in key
        t = make_table.makeTable(text) #the table that determines where a search must kick off after a failure

        while m+i < len(text):
                if key[i] == text[m+i]:
                        i = i+1
                        if i == len(key):
                                return m
                else:
                        m = m + i – t[i]
                        if i > 0:
                                i = t[i]

        return "not found"

Here is the snippet that helps backtrack:

#!/usr/bin/env python
#Author: Shriphani Palakodety
#Mail: shriphani@shriphani.com
#Mail2 = spalakod@purdue.edu
#File: make_table.py

def makeTable(text, num_list=[-1,0]):

        position = 2
        cnd = 0

        while position < len(text):
                if text[position – 1] == text[cnd]:
                        num_list.append(cnd +1)
                        position = position+1
                        cnd = cnd + 1

                elif cnd >0:
                        cnd = num_list[cnd]

                else:
                        num_list.append(0)
                        position = position + 1

        return num_list

Now, I’ve got to find more coffee and finish a discrete math worksheet…

About this entry

You’re currently reading “Knuth Morris Pratt String Searching,” an entry on Shriphani Palakodety

Published:
12.06.08 / 11am
Category:
Computer Science, python