什么是字符串匹配？
给你一个字符串str，问你这个字符串中是否包含字符串sub。例如：str="abcdef"，sub="cdef"，问str中是不是有sub。
一.BF算法
BF算法（Brute Force），翻译成中文就是暴力匹配算法。
暴力匹配其实很好想，不就让我们判断str中有没有sub嘛，直接一个一个来。定义两个指针，一个指str，一个指sub。如果两个字符相同，继续匹配下一个；不同，sub的指针从头再来，str的指针指到开始位置的下一个（因为开始位置已经匹配不上了，肯定要从下一个开始啦）。
boolean BruteForce(String str,String sub){
//定义两个指针,cur1指向str,cur2指向sub
int cur1=0,cur2=0;
int n=str.length();
int m=sub.length();
while(cur1<n && cur2<m){
if(str.charAt(cur1)==sub.charAt(cur2)){
cur1++;
cur2++;
}else{
cur1=cur1-cur2+1;
cur2=0;
}
}
if(cur2==m){
return true;
}else{
return false;
}
}我给出的代码只是一个思路，实际使用根据情况来。比如我们实际需要能跟str匹配上sub的起始下标，那方法返回的就是整形就行。
BF算法很简单，而且它不是本文的重点，所有就不过多赘述了。
二.KMP算法
KMP算法是本文的重中之重。关于KMP算法的由来，历史什么的这里就不说了，感兴趣的可以自己查一下。
我们先前使用的BF算法匹配，这个算法有个致命的缺点，那就是每次没匹配上，都要从头再来，很烦，时间复杂度很高（O（n*m））。
我之前写过一篇文章介绍过马拉车（Manacher）算法，马拉车（Manacher）算法就是重复利用了回文串的特性来优化时间复杂度的。其实这个的思路也是一样的，我们使用BF算法的时候，没有很好的利用字符串告诉我们的信息。
要想理解KMP算法，有个很重要的东西要先介绍一下，部分匹配表（Partial Match Table）。其实大家不理解KMP算法的主要原因就是这个部分匹配表。这个表中记录了什么数据这里先不管，我先让大家明白这里的数据是怎么来的。
这里其实有点对称意思，什么意思呢，看这个图：
我们在匹配到了a的时候发现，完了，sub是f，匹配失败了。这里我们要充分利用字符串的信息，我们看f前面是不是有个abc，注意啊，str上面也有一个abc，这是跟f前面abc一一对应的（已经匹配上的）。如果说sub的开头也是这个话，那是不是我们就不用让str从开始位置的下一个开始了呢，直接从这个位置开始（也就是图上箭头指向a的位置）。
为什么？我们画线部分的内容都是匹配好的，都是一一对应的 --> sub的f前有一个abc，str的a前也有一个abc --> sub的开头也是abc --> str的a前的abc直接就与sub开头的abc匹配好了：
我们下次匹配str直接从a开始，sub直接从e开始，大大提高了效率。
有人可能会问，这不凑巧了吗？恰好sub的开头是sub。对！要的就是这个“巧”，要的就是凑巧。
那我们怎么去知道有没有“凑巧”这种情况呢？下面先引出前缀和后缀的概念。
先举个例子：abcde，它的前缀：a,ab,abc,abcd，它的后缀：e,de,cde,bcde。很好理解吧，注意这里的前缀和后缀没有包含其本身即abcde。
说这个有什么用呢？其实我们的部分匹配表就是通过这个求出的。部分匹配值就是前缀和后缀的最长的共有元素的长度。
举个例子：abcdabc，它的前缀：a,ab,abc,abcd...，它的后缀：c,bc,abc,dabc...。从中我们可以得到最长的共有元素的长度为3，即abc。
如果我们用上面图的例子，可以得到sub的部分匹配表值如下：
回到上面我说的这里有点对称的意思，可以前缀和后缀的最长的共有元素的长度，不就是对称的分布在字符串的头和尾，不过这个对称可能不是严谨的对称，只是我们对这个现象的简单总结。
那部分匹配表有什么用呢？它可以求出我们sub应该后退到的位置。比如上面的c下面的3，意味着在f这里不匹配，我们可以回退到e的位置。
为什么在实际写代码的时候会定义一个next数组来存储部分匹配表。
//next数组的求取方法
public int[] getNext(String sub){
int m=sub.length();
int[] next = new int[m];
for(int i = 1 , j = 0; i < m ; i ++ ){
while(j > 0 && sub.charAt(i) != sub.charAt(j)) {
j = next[j - 1];
}
if(sub.charAt(i) == sub.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}有了next数组后相当于我们知道了当不匹配时，sub的指针j回退到什么位置。思路与上面的BF算法的思路相同，但是这里我们不用回退str的指针i，同时，sub的指针j不用回退到0的位置。
//匹配str中的sub，把匹配成功的下标返回
public List<Integer> KMP(String str,String sub){
int n=str.length();
int m=sub.length();
List<Integer> result=new ArrayList<>();
int[] next = getNext(sub);
for(int i = 0 ,j = 0 ; i < n ; i ++ ){
while(j > 0 && str.charAt(i) != sub.charAt(j)) {
j = next[j - 1];
}
//相等就++，往后找
if(str.charAt(i) == sub.charAt(j)) {
j++;
}
if(j == m){
//sub遍历完，记录下标，同时回退sub
result.add(i - m + 1);
j = next[j-1];
}
}
return result;
}三.Z函数（扩展KMP）
Z函数，又叫扩展KMP，但其实跟KMP没有任何关系。Z函数也是用来处理字符串匹配问题的方法。我们定义一个z数组，z[i]表示从 s[i] 到 s[n−1] 的子串与整个字符串s的最长公共前缀的长度。
举个例子，abeabc：
当我们求下标为3的z（图上箭头指向的位置）时，我们用红色画线与蓝色画线（整个字符串）进行匹配，最长公共前缀是ab，长度是2，所以z[3]=2。
public int[] getZ(String s) {
int n=s.length();
int[] z=new int[n];
int l = 0, r = 0;
for (int i = 1; i < n; i++) {
if (i <= r) {
z[i] = Math.min(z[i - l], r - i + 1);
}
while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) {
l = i;
r = i + z[i];
z[i]++;
}
}
return z;
}