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:
#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:
#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…
No Comments so far ↓
There are no comments yet...Kick things off by filling out the form below.