JavaOJ 题集 & 字符串匹配问题 & BF算法 & KMP算法
背景（from百度百科）：
BF算法，即暴力(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) [1] 。
大抵意思就是，字符串找子串咯！
就是，给一个字符串s1和一个子字符串s2，在s1里找到与s2完全一样的一个片段。
【力扣28原题链接】
1. BF暴力算法
这种方法简单粗暴，如下图
原字符串每个下标都尝试一下，每次错误（图示为了简约写为 j ，代码为了明确写为 subI）subI都置为0，从头测试，
如果最终subI都没有达到子字符串的长度，那么就返回-1【即不存在】，
否则返回 i - subI
【即该子字符串在原字符串的头下标】
【因为i与subI走的步数一致】
public static int BFMatch(String str, String subStr) { //预防一些奇葩事例 if(str == null || subStr == null || str.length() == 0 || subStr.length() == 0) { return -1; } int i = 0; int subI = 0; while(i < str.length() && subI < subStr.length()) { //相同一起走一步 if(str.charAt(i) == subStr.charAt(subI)) { i++; subI++; }else { //i要回退 i = i - subI + 1; //subI要回退为初始位置0 subI = 0; } } return subI == subStr.length() ? i - subI : -1; }
1.1 测试
public static void main(String[] args) { System.out.println(BFMatch("mississippi", "issip")); }
2. KMP算法
在之前的计算之中，我们的subI都直接清0，但是实际上，应该是有一部分还可以保留
如下图：
没错，subI并没有直接清为0，而是找到了前面可以用的一部分，继续走，而【i】，从始至终都从未回退！
要实现这个算法，很重要的一个点就是，subI回退到哪？
我们需要一个next数组来记录subStr的每一个停下的话要回退到哪。
接下来我们来研究一下其中的规律吧！
2.1 基础模板
阻隔一些特殊用例
两个下标
两个字符串长度，避免反复使用 length() —>提高效率
转化为两个字符串数组，避免反复使用charAt() —> 提高效率
得到next数组
getNext(next, subStrArr, subLen);
匹配一下
subI = next[subI]; ===》subI的回退 public static int strStr(String str, String subStr) { //1.*********************** if(str == null || subStr == null || str.length() == 0 || subStr.length() == 0) { return -1; } //2.*********************** int i = 0; int subI = 0; //3.*********************** int strLen = str.length(); int subLen = subStr.length(); //4.*********************** char[] strArr = str.toCharArray(); char[] subStrArr = subStr.toCharArray(); //5.*********************** int[] next = new int[subLen]; next[0] = -1; if(subLen != 1) { getNext(next, subStrArr, subLen); } //6.*********************** while(i < strLen && subI < subLen) { if(subI == -1 || strArr[i] == subStrArr[subI]) { i++; subI++; }else { subI = next[subI]; } } return subI == subLen ? i - subI : -1; }
2.1.1 获得next数组
理论基础：
设数字k为其跳回的位置， i为停下来的位置
那么字符串 【0 ，k - 1】对应的就是subStr停下来前的一小段【i - k, i - 1】（重点）
注意：subStr停下的那个位置，之前有k个在原字符串对应位置走过！
注意：两小段可以相交但是不能相等！，否则跟没回退一样，等着死循环吧
即，这一段与原字符串对应位置一致
如下所示
那么 k 对应的值就是前面重复部分的长度【三种值， -1 ， 0 ， > 0】【-1, 就是首元素的回退，当然使用的时候要判断一下，避免数组越界访问】
接下来我们要来看看如何求具体某一个下标对应的next值
假设，我说假设！
如果我知道一个 next[X - 1]，next[X]可以求吗？
如果可以的话，是不是就可以通过 递推：next[0] --> next[1] -->next[2] —> … —> next[X]
如上图，要求next[X],知道next[X - 1],怎么求 next[X] 呢?
Ⅰ.如果 k == next[x - 1],满足 subStr.charAt( k ) == subStr.charAt(X - 1)
有如下关系（伪代码）
【0, k -1】 + 【k - 1， k】 == 【i - k, i - 1】 + 【i - 1, i】;
也就是
【0, k】 == 【i - k, i】;
所以next[X] = k + 1
Ⅱ. 如果不相等，则说明 “不能-少-回退那么多”，要 “多回退一点”
我们只需要让next[k]再回退几次，直到与满足上面情况，或者无法再回退，【-1的设计就是为了如此】
如下图（特别重要！）
理论基础就是：本质上递推求next[X]，的原理就是，
【红串】 == 【橙串】，相当于两段字符串以及完美匹配了，
最后，我们再加上一个元素，如果不匹配！== 》
则【红串】（类比，subStr）的尾倒退一次，
【橙串】也减低了要求，不需要匹配那么远了，也没办法匹配那么远
这张图的结束就是===》next[X] = 0
2.1.2 代码实现
int[] next = new int[subLen]; next[0] = -1; if(subLen != 1) { //只有一个字符就不需要这个方法了 getNext(next, subStrArr, subLen); } public static void getNext(int[] next, char[] arr, int len) { //白手起家 int k = 0; //白手起家所需要的原材料，把值能确定的先赋值上 //这种【递推思想】的题，有原材料做起来会更好，好比珍珠成型之前也需要一颗小石子 next[1] = 0; int i = 2; //遍历每一位 while(i < len) { //相等或者无法再次回退 if(k == -1 || arr[i - 1] == arr[k]) { next[i] = k + 1; i++; k++;//k变长 }else { k = next[k];//k变短 } } }
2.1.3 测试
成功
如果不转化为字符数组，是没办法达到 0ms 的；
3. KMP算法优化版
还记不记得这张图？
没错，我们发现了一些赘余部分，
就是19跳到15,还是d，还是得回退，接下来可以直到15跳到11，还是d！，
这样下去跳到 3，接下来就是 0，既然如此为什么不直接到 0呢？
接下来我们设计一个方法getNextValue()，去修改一些next值，避免上面的状况
public static int[] getNextValue(int[] next, int len, char[] arr) { int[] nextValue = new int[len]; nextValue[0] = -1; //遍历整个数组 for (int i = 1; i < len; i++) { int n = next[i]; if(arr[i] == arr[n]) { nextValue[i] = nextValue[n]; }else { nextValue[i] = n; } } return nextValue; }
3.1 如果回退后的字符跟回退前一致
if(arr[i] == arr[n]) { nextValue[i] = nextValue[n]; }
那么继承回退后的那个nextValue对应值
3.2 如果回退后的字符跟回退前不一致
else { nextValue[i] = n; }
保留自己的next对应值
3.3 测试
//在strStr()方法，匹配前，补充上如下代码,并之后使用next的都改成使用nextValue;
int[] nextValue = getNextValue(next, subLen, subStrArr);
文章到此结束！谢谢观看
可以叫我 小马，我可能写的不好或者有错误，但是一起加油鸭🦆！
这是我的代码仓库！（在马拉圈的23.2里）代码仓库
字符串匹配算法 · 具体位置
邮箱：2040484356@qq.com
