1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/kmp.py Mon Jul 04 16:41:40 2011 +0200
1.3 @@ -0,0 +1,44 @@
1.4 +"""
1.5 +Author: Eugen Sawin <sawine@informatik.uni-freiburg.de>
1.6 +"""
1.7 +
1.8 +def main():
1.9 + args = parse_arguments()
1.10 + print "next ", next(args.pattern)
1.11 + print kmp(args.text, args.pattern)
1.12 +
1.13 +def kmp(text, pattern):
1.14 + l = []
1.15 + n = next(pattern)
1.16 + j = 0
1.17 + for i in range(len(text)):
1.18 + while j >= 0 and text[i] != pattern[j]:
1.19 + #print "mismatch at text %i and pattern %i" % (i, j)
1.20 + #print "new pattern %i" % (n[j],)
1.21 + j = n[j]
1.22 + j += 1
1.23 + if j == len(pattern):
1.24 + l.append(i - len(pattern) + 1)
1.25 + j = n[j]
1.26 + return l
1.27 +
1.28 +def next(pattern):
1.29 + n = [-1]
1.30 + j = -1
1.31 + for i in range(len(pattern)):
1.32 + while j >= 0 and pattern[i] != pattern[j]:
1.33 + j = n[j]
1.34 + j += 1
1.35 + n.append(j)
1.36 + return n
1.37 +
1.38 +from argparse import ArgumentParser
1.39 +
1.40 +def parse_arguments():
1.41 + parser = ArgumentParser(description="KMP.")
1.42 + parser.add_argument("text", help="the text")
1.43 + parser.add_argument("pattern", help="the pattern")
1.44 + return parser.parse_args()
1.45 +
1.46 +if __name__ == "__main__":
1.47 + main()