2023年7月20日发(作者：)

寻找⼦串：BF算法、回溯算法、KMP算法⼀、前⾔查找⼦串，是字符串查找的经典题⽬，⼤学就有！⽐如：主串：『ABAEABDACAADABACDDA』中查找⼦串：『ABACD』不考虑性能（时间、空间复杂度），⼤家可能就直接⽤暴⼒来求解了：Brute-Force（BF）、Back-Track（BT）；但如果要求有⼀定的性能，那么 KMP ⽆疑是最经典的算法了（虽然不⼀定是效率最⾼的）⼆、BF算法// BF暴⼒算法private static int bruteForce(String s, String p) { int i = 0; for (; i < () - () + 1; i ++) { int j = 0; for (; j < (); j ++) { if ((i + j) == (j)) { continue; } break; } if (j == ()) { return i; } } return -1;}三、BT算法// BT回溯算法private static int backTrack(String s, String p) { int i = 0, j = 0; while (i < () && j < ()) { if ((i) == (j)) { j ++; } else { i -= j; j = 0; } i ++; } return j == () ? i - j : -1;}四、KMP算法我们先来通过主串与⼦串的查找来找找规律：再来看另⼀个数据多点的例⼦：『C』与『B』不匹配时，滑动⼦串，因为，有共同的前缀『AB』，所以，只需要从⼦串『index = 2』开始⽐较就⾏，如下图：⾄此我们可以⼤概看出⼀点端倪，当匹配失败时，j要移动的下⼀个位置k。存在着这样的性质：最前⾯的k个字符和j之前的最后k个字符是⼀样的。如果⽤数学公式来表⽰是这样的 ：P[0 ~ k-1] == P[j-k ~ j-1]这个相当重要，如果觉得不好记的话，可以通过下图来理解（即 P[j]发⽣不匹配时，滑动到k的位置，⽐较P[k]）：主串S 与 ⼦串P 在 j 处发⽣不匹配时，为什么可以移动到位置 k 推导：1. S[i] != P[j]时，必然存在：S[i-j ~ i-1] == P[0 ~ j-1]；2. P中存在⼀个k，使得：P[0 ~ k-1] == P[j-k ~ j-1]；3. 那么：S[i-k ~ i-1] = P[0 ~ k-1]如果求 k ？我们需要借助⼀个数组，来记录当每个位置发⽣不匹配时，需要滑动到的位置，如下图：Next 就是⼀个记录的数组（前缀数）：初始标记： next[0] = -1；next[k] = 相同前缀的字符个数;当 p[j] != p[k] 时， k = next[k] （直观就看下图：『C』和『B』）// j为不匹配时的下标，k下标对应的是// 串[0 ~ k-1] = 串[j-k ~ j-1]private static int[] getNext(String p) { int next[] = new int[()]; int k = -1, j = 0; next[0] = -1; while (j < () - 1) { if (k == -1 || (j) == (k)) { next[++j] = ++k; } else { k = next[k]; // next数组中前K个元素，已经有前缀统计 } } return next;}KMP最终算法如下// KMP算法private static int kmp(String s, String p) { int next[] = getNext(p); int i = 0, j = 0; while (i < () && j < ()) { if (j == -1 || (i) == (j)) { i ++; j ++; } else { j = next[j]; } } return j == () ? i - j : -1;}