针对字符串匹配问题：
暴力的匹配方式莫过于，从前到后，一一对比判断，从长度为n的目标串(记：target)，匹配到长度为m模版串(记：pattern)
时间复杂度为O(m*n)
KMP算法：
KMP算法则不用一步步的向前移动匹配，可以计算出一个next数组（跳转表），快速的匹配。
计算next的复杂度为m，运用next表对目标字符串匹配的复杂度为n
时间复杂度为O(m+n)，效率提高极为显著
KMP算法匹配过程：
1.求出next，next表是根据pattern来求，考虑到是模版字符串中，最大相等字符子串的长度，String pattern="abcabcacab"; 这里拿出经典的字符串来计算并说明：
next计算方式，红色字符表示要计算的子字符串，依次算出patten的十个跳转数字（提示：后面匹配过程中，匹配失败后，前移的长度为：匹配失败的index-next）
前后缀最大相等字符子串的长度=0
前后缀最大相等字符子串的长度=0
前后缀最大相等字符子串的长度=0
前后缀最大相等字符子串的长度=1
前后缀最大相等字符子串的长度=2
前后缀最大相等字符子串的长度=3
前后缀最大相等字符子串的长度=4，注意：abca
前后缀最大相等字符子串的长度=0
前后缀最大相等字符子串的长度=1
前后缀最大相等字符子串的长度=2
2.匹配：目标字符串String target="babcbabcabcaabcabcabcacabc"; 向前移动的距离为pattern的index-next，（注：index的起始为1）
原文：http://www.cnblogs.com/winv758241/p/7095156.html