对于字符串匹配，暴力法是对每个位置进行逐位匹配，只要有匹配失败的，就从待匹配串的下个位置开始从头匹配，这样的时间复杂度是O（MN）。 KMP算法能解决这样效率低下匹配，其核心思想是保留已匹配的前缀和，避免重复匹配，时间复杂度是O（M+N）。
举例来说，有一个字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一个字符串"ABCDABD"？
首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。 因为B与A不匹配，搜索词再往后移。 直到字符串有一个字符，与搜索词的第一个字符相同为止。 接着比较字符串和搜索词的下一个字符，还是相同。 直到字符串有一个字符，与搜索词对应的字符不相同为止。 这时，如果使用暴力法，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率极低，因为把"搜索位置"移到已经比较过的位置，重比一遍。 当空格与D不匹配时，其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。 可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2 因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（“AB”），对应的"部分匹配值"为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。 因为空格与A不匹配，继续后移一位。 逐位比较，直到发现C与D不匹配。 逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。 "部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，
"A"的前缀和后缀都为空集，共有元素的长度为0；"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；“ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A”，长度为1；“ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB”，长度为2；"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。KMP算法的Java实现
class Main { public int KMP(String s1, String s2){ if(s2.length()>s1.length() || s2.length()==0) return -1; int i=0,j=0; int[] next = getNextArray(s2); while(i<s1.length()){ if(s1.charAt(i)==s2.charAt(j)){ i++; j++; if(j==s2.length()) return i-j; }else{ if(next[j]==-1) i++; else j=next[j]; } } return -1; } public int[] getNextArray(String s){ int[] next = new int[s.length()]; next[0]=-1; for(int i=1;i<s.length();i++){ int j=next[i-1]; while(j!=-1){ if(s.charAt(i-1) == s.charAt(j)){ next[i]=++j; break; }else j=next[j]; } } return next; } }