Lab Week 7

Imported Code

Project Code

def BMSearch(pattern, string, printer=False): found = False l = [0]*26 a = list("abcdefghijklmnopqrstuvwxyz") pattern = list(pattern) pattern.reverse() string = list(string) i = len(pattern) for j in range(len(a)): try: l[j] = i - pattern.index(a[j]) - 1 except: l[j] = -1 pattern.reverse() if printer: print l j = 0 while j <= len(string) - len(pattern): if printer: print j, pattern, string[j:j+len(pattern)] for k in range(len(pattern) - 1, -1, -1): if string[j + k] != pattern[k]: n = l[a.index(string[j+k])] if n == -1: j += (k) elif k - n > 0: j += (k - n - 1) break if k == 0: print("Pattern is found at index %d" % j) found = True j += 1 return found

Commands

print BMSearch("ab", "abracadabra", True) print '' print BMSearch("abc", "abracadabra", True)

Output

Imported Code

Project Code

def hasher(x, pattern, m, q): thishash = 0 for i in range(m): thishash *= x thishash += ord(pattern[i]) return thishash % q def rehasher(thishash, outgoing, xx, x, incoming, q): thishash -= (ord(outgoing) * xx) thishash *= x thishash += ord(incoming) return thishash % q def RKSearch(pattern, string, printer=False, x=1, q=1000): found = False m = len(pattern) comphash = hasher(x, pattern, m, q) currhash = hasher(x, string, m, q) xx = x ** (m - 1) for i in range(len(string) - m + 1): if printer: print i, comphash, currhash if comphash == currhash: for j in range(m): if pattern[j] != string[i + j]: break print("Pattern is found at index %d" % i) found = True try: currhash = rehasher(currhash, string[i], xx, x, string[i + m], q) except: return found

Commands

print RKSearch("ab", "abracadabra", True) print '' print RKSearch("abc", "abracadabra", True)

Output

Imported Code

Project Code

class trieNode: def __init__(self, value=None, parent=None, superroot=True): self.value = value self.nodes = [] self.parent = parent self.superroot = superroot def clearTree(self): if self.superroot: self.nodes = [] def insertWord(self, w): if self.superroot: w = list(w) w.append('$') if len(w) == 0: return for i in range(len(self.nodes)): if self.nodes[i].value > w[0]: self.nodes.insert(i, trieNode(w[0], self, False)) if self.nodes[i].value == w[0]: self.nodes[i].insertWord(w[1:]) return i = len(self.nodes) self.nodes.insert(i, trieNode(w[0], self, False)) self.nodes[i].insertWord(w[1:]) def searchPrefix(self, w): if self.superroot: w = list(w) if len(w) == 0: return True for n in self.nodes: if n.value == w[0]: return n.searchPrefix(w[1:]) return False def searchWord(self, w): if self.superroot: w = list(w) w.append('$') return self.searchPrefix(w) def countPrefix(self, w): if self.superroot: w = list(w) if len(w) == 0: return self.countChildren() for n in self.nodes: if n.value == w[0]: return n.countPrefix(w[1:]) return 0 def countChildren(self): if self.value == '$': return 1 count = 0 for n in self.nodes: count += n.countChildren() return count def _deleteWord(self, w): if self.superroot: w = list(w) w.append('$') if len(w) == 0: return True for i in range(len(self.nodes)): n = self.nodes[i] if n.value == w[0]: deleted = n._deleteWord(w[1:]) if len(n.nodes) == 0: if deleted: self.nodes.pop(i) return True return False return False def deleteWord(self, w): self._deleteWord(w) def printWords(self, printString=""): if self.value == '$': print(printString) letter = "" if self.value is not None: letter = self.value for n in self.nodes: n.printWords(printString + letter) def insertArray(self, a): if not self.superroot: self.parent.insertArray(a) return for w in a: self.insertWord(w) def insertFile(self, filename): f = open(filename) l = f.read() l = l.split() self.insertArray(l) def suffixTrie(self, w): if self.superroot: w = list(w) for i in range(len(w)): self.insertWord(w[i:])

Commands

trie = trieNode() trie.suffixTrie("abracadabra") print trie.countChildren() print '' trie.printWords()

Output