文章目录
- 1. 暴力匹配算法BF
- 2. KMP算法
- next数组求法
- Java代码：
- C++代码：
- KMP算法优化nextval数组
1. 暴力匹配算法BF
在了解KMP算法前，就必须介绍串的暴力匹配算法（BF算法）
BF算法，即暴力(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。
如果字符匹配，i和j同时向前移动，同时还需要一个变量记录i的初始位置pos。
如果j走到了字符末尾，说明字符串匹配，返回pos即可
否则说明字符串不匹配，j退回原字符串的起始，i变成pos的下一个位置，并且更新pos的值
很容易看出，暴力匹配的算法时间复杂度为O(N2)
C++代码如下：
#include <string>#include <iostream>using namespace std;/*** @brief 字符串暴力匹配算法** @param src 源字符串* @param dst 需要匹配的字符串* @return int 返回第一次出现要匹配的子串的位置，下标从0开始*/
int BF(const string &src, const string &dst)
{if (src.size() == 0 || dst.size() == 0){return -1;}int posSrc = 0;int posDst = 0;while (posSrc < src.length() && posDst < dst.length()){if (src[posSrc] == dst[posDst]){posSrc++;posDst++;}else{//回退posSrc = posSrc - posDst + 1;posDst = 0;}}//说明匹配到最后的字符了,返回第一次出现字串的位置if (posDst == dst.length()){return posSrc - posDst;}else{return -1;}
}int main()
{// cout << BF("abcabcabcdabcde", "abcd") << endl;cout << BF("abcdabcabcdabcde", "abcd") << endl;return 0;
}
2. KMP算法
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。
KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次
数以达到快速匹配的目的。
具体实现就是通过一个next数组实现，这个数组本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)
KMP算法于BF算法最大的不同点是：
匹配失败后主串的 i 并不会回退，j也不会直接回到0号位置
eg:
首先如果两个串字符匹配的话就同步向前走
BF算法i就直接回退到1位置，就回退到0位置。实际上并不需要，因为这次一定不可能匹配。
i不回退，这里的最优回退是j回退到2位置。 KMP算法关键就是找j回退到那里。
因为KMP算法本身要求i不会退。所以，需要尽量在已经匹配的主串中找到和字串匹配的部分。
j回退的位置是需要查询next数组的。
next数组定义：保存字串某个位置匹配失败后回退的位置。
next数组的下标就是匹配失败的字符在字串的位置，对应下标的值就是j需要回退的位置。
next数组求法
-
找到匹配成功部分的两个相等的真子串（不包含本身），一个以下标 0 字符开始，另一个以 j-1 下标字符结尾。
eg：
-
找到两个真字串的长度就是这位置匹配失败回退的位置。找不到两个回退位置就是0
-
不管什么数据 next[0] = -1 next[1] = 0
练习：
下标：0 1 2 3 4 5 6 7 8 9 10 11 12 13a b a b c a b c d a b c d e
next[0]=-1 next[1]=0
next[2]：0下标对应字符为a 1下标对应字符是b 找a开头b结尾的两个真字串next[2]=0（因为2下标前的匹配字符串找不到复合条件的两个真串）
next[3]：0下标对应字符为a ，2下标对应字符是a。找a开头a结尾的两个真字串next[3]=1 (找到的两个真字串长度为1)
next[4]=2；next[5]=0；next[6]=1；next[7]=2；next[8]=0...
next数组为[-1 0 0 1 2 0 1 2 0 0 1 2 0 0]
-----a b c a b c a b c a b c d a b c d e
next数组：
[-1 0 0 0 1 2 3 4 5 6 7 8 9 0 1 2 3 0]
特别注意：找两个相同的最长真字串时，第一个字串必须从0下标开始，第二个字串结尾固定是j-1位置，不能在其他位置找。
如果要实现代码，需要根据next[j]求next[j+1]的值
Java代码：
public class KMP {public static void InitNext(String dst, int[] next) {next[0] = -1;next[1] = 0;int k = 0;for (int i = 2; i < dst.length(); i++) {// 找str[i-1]==str[k]位置while (k != -1 && dst.charAt(i - 1) != dst.charAt(k)) {k = next[k];}next[i] = k + 1;}}// 使用KMP算法返回src第一个匹配dst的位置,下标从0开始,从src的pos位置开始匹配public static int GetSubStrPos(String src, String dst, int pos) {if (src == null || dst == null || src.length() == 0 || dst.length() == 0)return -1;if (pos >= src.length() || pos < 0)return -1;int i = pos;// 遍历src主串int j = 0;// 遍历dst字串int lenSrc = src.length();int lenDst = dst.length();// 计算字串的next数组int[] next = new int[lenDst];InitNext(dst, next);while (i < lenSrc && j < lenDst) {if (j == -1 || src.charAt(i) == dst.charAt(j)) {//j==-1代表第一个字符就匹配失败，i从第二个字符开始匹配，j从0开始i++;j++;} else {// i不回退j = next[j];}}if (j >= lenDst) {// 匹配成功，返回i-jreturn i - j;} else {return -1;}}public static void main(String[] args) {// System.out.println(GetSubStrPos("abcabcabcdabcde", "abcd", 0));System.out.println(GetSubStrPos("abcdabcabcdabcde", "abcd", 1));}
}C++代码：
#include <string>
#include <iostream>
#include <vector>
#include <assert.h>using namespace std;//使用KMP算法返回src第一个匹配dst的位置,下标从0开始,从src的pos位置开始匹配void InitNext(const string &dst, vector<int> &next)
{next[0] = -1;next[1] = 0;int k = 0;for (int i = 2; i < dst.size(); i++){while (k != -1 && dst[i - 1] != dst[k]){k = next[k];}next[i] = k + 1;}
}int KMP(const string &src, const string &dst, int pos)
{assert(pos >= 0 && pos < src.length() && src.size() > 0 && dst.size() > 0);int i = pos;int j = 0;int srcSize = src.size();int dstSize = dst.size();vector<int> next(dst.size(), -1);InitNext(dst, next);while (i < srcSize && j < dstSize){if (j == -1 || src[i] == dst[j]){i++;j++;}else{j = next[j];}}if (j == dst.size()){return i - j;}else{return -1;}
}int main()
{// cout << KMP("abcabcabcdabcde", "abcd", 0) << endl;// cout << KMP("abcdabcabcdabcde", "abcd", 0) << endl;cout << KMP("abcdabcabcdabcde", "abcd", 1) << endl;return 0;
}
KMP算法优化nextval数组
nextval数组对KMP算法的优化在于：
原KMP算法，求next数组是一个循环，需要一步一步找到str[i]==str[k]的位置。
nextval数组就是对这一步一步找str[i]==str[k]的优化。
nextval数组生成规则：
- 先根据next数组生成规则计算值这就是不匹配需要回退的位置。
- 如果当前回退的位置，正好是和当前字符一样，那么就写那个字符的nextval值。不一样就写原来的next数组的值。
