(六)Brute

public static int bruteforce(String source, String sub) { int j = 0, i = 0,index=-1; while (i < source.length()="" &&="" j="">< sub.length())="" {="" if="" (source.charat(i)="=" sub.charat(j))="" {="" i++;="" j++;="" }="" else="" {//="" 使i回退到下一个字符，应为子串的前面j向可能匹配成功，而第j+1项失败，所以="" i="i-j+1" i="i" -="" j="" +="" 1;="" j="0;" }="" }="" if="" (j="=" sub.length())="" {="" index="i" -="" sub.length();="" }="" else="" {="" index="-1;" }="" return="" index;="">

Brute-Force算法总结：

该方法的优点是：算法简单明朗，便于实现记忆。

缺点是：进行了回溯，效率不高，而这些都是没有必要的。比如下图：

KMP算法

Brute-Force被称为简单模式匹配算法。KMP算法是它的改进算法。

一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此称之为KMP算法。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作，其基本思想是：每当匹配过程中出现字符串比较不等时，不需回溯指针，而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离，继续进行比较。

模式串求最大真子串

例如：求aaaab next[j]。

计算模式串的next[j]

当Si≠Tj,若模式串存在最大真子串，可将模式串T按照k=next[j]的值向右滑动，然后比较Si和Tk，若仍有Si≠Tk,则模式串T按照新的k=next[j]的值向右滑动后比较。这样的过程一直进行到k=next[k]=0,此时若Si≠T0,则模式串T不再向右滑动，随后比较Si+1和T0。

例如：主串为'aaaaaaab',子串为'aaaab',求采用KMP的模式匹配过程。

//KMP算法public class KMP { //根据给定的模式串，求next[j]的算法 public static int[] getNext(String sub) { int j=1,k=0; int[] next = new int[sub.length()]; next[0]=-1; next[1]=0; while(j<>