TU Wien:Algorithmen und Datenstrukturen 2 VU (Raidl)/Knuth-Morris-Pratt Boyer-More Hilfsskripte

• AD2 SS13
  • Übung 2 UE2

Knuth-Morris-Pratt

initNext

laut Skriptum, python implementation

def initNext(P):
        P = " "+P
	next = list()
	for x in range(0, len(P)):
		next.append(0)
	next[1] = 0
	l = 0
  	for q in range(2, len(P)):
		while (l > 0 ) and (P[l+1] != P[q]):
			l = next[l]
		if P[l+1] == P[q]:
			l = l+1
		next[q] = l
	return next[1:]

aufzurufen

Pattern = "DBDDBDBD"
next = initNext(Pattern)

Boyer-More

initSuffix

berechnet suffix array mithilfe der initNext funktion, gibt dabei alle notwendigen rechenschritte übungsfreundlich aus.

• depends on initNext(P)

def initSuffix(P):
	print "initSuffix(%s)" % P
        P = " "+P
	i = len(P)-1
	Pinv = " "
	suffix = [0]
	while i > 0:
		Pinv = Pinv + P[i]
		suffix.append(0)
		i = i-1
	next = initNext(P)
	print "next is: "
	print next
	nextInv = initNext(Pinv)
	print "next inverted is: "
	print nextInv
	#print next, nextInv
	M = len(P)-1
	for j in range(1, len(P)):
		suffix[j] = M - next[M-1]
		print "suffix an der stelle %d ist M - next[%d] = %d" % (j, M, suffix[j])
	print ""
	for q in range(1, M+1):
		print "fuer q = %d" % q
		j = M - nextInv[q-1]
		print "j = M - nextInv[%d] = %d - %d = %d" % (q, M, nextInv[q-1], j)
		if suffix[j] > (q - nextInv[q-1]):
			print "  suffix[%d] > (%d - nextInv[%d]) " % (j, q, q)
			print "  %d > (%d - %d) " % (suffix[j], q, nextInv[q-1])
			suffix[j] = q - nextInv[q-1]
			print "  >>> suffix[%d] = %d" % (j, (q-nextInv[q-1]))
		print ""
	return suffix[1:]

aufruf in python

Pattern = "BBACAC"
print initSuffix(Pattern)

---

beware of bugs in the above code, only proved it correct not tried it, maxl