??串(又称字符串)是由n(n≥0)个字符组成的有限序列，它是数据元素为单个字符的特殊线性表。串可以用顺序存储方式或者链式存储方式进行存储。模式匹配是串最重要和最复杂的一个操作，其实也就是串的查找，其中Brute-Force算法和KMP算法是两种最经常使用的顺序存储结构下的串的模式匹配算法。
??模式匹配操作的具体含义是：
??在主串（也称做目标串)S中，从位置start开始查找是否存在子串(也称做模式串)T，如果在主串S中查找到一个与模式串T相同的子串，则称查找成功；如在主串S中未找到一个与模式串T相同的子串，则称查找失败。当模式匹配成功时,函数返回模式串T的第一个字符在主串S中的位置;当模式匹配失败时,函数返回-1。
??实际上，这就是C语言的 strstr() 以及 Java的 indexOf()函数实现的功能。
??BF算法的主要思想是：将主串S的第start个字符和模式T的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串S的下一字符起，重新与T第一个字符比较，直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值 –1。
代码实现：
public int BFindex(String S,int start,String T){
int i=start,j=0,v;
while(i<S.length() && j<T.length()){
if(S.charAt(i)==T.charAt(j)){
i++;
j++;
}
else{
i=i-j+1; //i的下一个，已经比较了j次，所以是i-j+1
j=0;
}
}
if(j==T.length()) //匹配成功
v=i-j;
else v=-1; //匹配失败
return v;
}??例如，主串T为：ababcabababab,子串为ababa,上述过程如下图所示。
??BF算法简单并且容易理解，但是有些情况下时间效率不高，最好情况下（一配就中）时间复杂度为O(m)，最坏情况下时间复杂度为O(n×m)。
??为了克服主串下标i在若干个字符序列比较相等后，只要有一个字符比较不相等便需要把下标i的值回退的缺点，提出了改进的匹配算法KMP。
??KMP算法的主要思想是：利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置，重点就在于当某一个字符与主串不匹配时，我们应该知道j指针要移动到哪里。
??这可以分为两种情况来考虑：当前si和tj比较不相等，（1）当模式串中不存在可相互重叠的真子串，下一次可直接比较si和t0；（2）当模式串中存在可相互重叠的真子串时，j要移动的下一个位置为k，k满足：模式串中最前面的k个字符和j之前的最后k个字符是一样的。
??所以，问题的重点：计算每一个位置j对应的k，所以用一个数组next来保存，next[j] = k，表示当S[i] != T[j]时，j指针的下一个位置。
求next的函数设计：
public void getNext(String T,int[] next){
next[0]=-1; //特殊值
int j=0,k=-1;
while(j<T.length()-1){
if(k==-1 || T.charAt(j)==T.charAt(k))
next[++j]=++k;
else
k=next[k];
}
}
??示意图如下：
public int KMP(String S,int start,String T,int [] next){
int i=start,j=0,v;
while(i<S.length() && j<T.length()){
if(S.charAt(i)==T.charAt(j)){
i++;
j++;
}
else if(j==0) i++;
else j=next[j];
}
if(j==T.length())
v=i-j;
else v=-1;
return v;
}??示意图如下：
原文：https://www.cnblogs.com/gzshan/p/10689760.html