KMP匹配算法,
原理参考http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
难点在于next数组的求解。
参考算法导论的思路求解next数组:
详见http://www.cnblogs.com/c-cloud/p/3224788.html
然后用Python实现了一下。
def makeNext(parttenString): next = [] m = len(parttenString) k = 0 next.append(0) p = 1 while p < m: while k > 0 and parttenString[k] != parttenString[p]: k = next[k - 1] if parttenString[k] == parttenString[p]: k += 1 next.append(k) p += 1 print "nextval = ",next return next def KMPAlgorithm(parttenString,rawString): nextval = makeNext(parttenString) isContain = False locationInRawString = 0 locationInparttenString = 0 lengthOfPartten = len(parttenString) lengthOfrawString = len(rawString) print lengthOfrawString,lengthOfPartten sameChar = 0 while isContain == False: print locationInRawString,locationInparttenString while locationInparttenString < lengthOfPartten and locationInRawString < lengthOfrawString and parttenString[locationInparttenString] == rawString[locationInRawString]: if locationInparttenString == lengthOfPartten - 1: isContain = True break else: locationInRawString += 1 locationInparttenString += 1 sameChar += 1 if lengthOfPartten - 1 == locationInparttenString and locationInRawString != lengthOfrawString - 1: break elif parttenString[locationInparttenString] != rawString[locationInRawString]: locationInRawString += 1 else: locationInparttenString = locationInparttenString - (sameChar - nextval[locationInparttenString - 1]) sameChar = 0 if locationInRawString >= lengthOfrawString: break return isContain if __name__ == "__main__": print KMPAlgorithm(‘CDAA‘,‘ABCDABCD‘)