题目描述
给你两个字符串 a 和 b ，要求输出从 b 中能找出多少和 a 相同的子串，允许有部分重叠。
串的模式匹配问题
给定一个主字符串S和模式串P，要求找出P在S中出现的位置，即为串的模式匹配问题。上题中的子串统计问题基本等同于串的模式匹配问题。
这里主要介绍两种串的模式匹配问题的解法，一种是暴力遍历的方法，另一种便是主要介绍的KMP算法。KMP算法其实之前在学校里上算法导论课的时候学过，今天主要是借刷题在拾起来，回顾一下。
暴力遍历子串统计
这个题目首先想到的方法肯定是从主串S的开头开始进行匹配尝试，然后往后顺移匹配尝试，如下图所示。这个方法的时间复杂度是O(n*m)，n是主串S的长度，m是模式串P的长度。
代码如下：
public static int subStringMatch(String large, String small) {
int len1 = large.length();
int len2 = small.length();
int count = 0;
for (int i=0; i<=len1-len2; i++) {
if (large.substring(i, len2+i).equals(small)) {
count += 1;
}
}
return count;
}
KMP子串统计
暴力遍历方法存一个比较明显的可以优化的地方，如下图所示，当匹配时出现模式串的第 i 位无法匹配的情况时，主串后移一位，并进行模式串的重新匹配。这里我们可以发现前4个字符"ABCD"实际上，我们已经知道。同时，模式串的内容我们也知道。KMP算法的意思就是利用这些已知信息，不进行模式串的从头匹配，而是设计方法从模式串的指定某个位置开始匹配。
在解释KMP的算法之前，先结合下图所示介绍KMP算法中会用到的两个概念。
字符串前缀
不包含字符串最后一个字符的，从字符串第一个字符串开始的连续子串。
字符串后缀
不包含字符串第一个字符的，从字符串第 i 个字符串开始到字符串结尾的连续子串。
next数组
KMP算法的关键内容next数组就是基于模式串的前缀和后缀计算得到的。具体地，next[j]，i = 0~P.length等于P[0]...P[j-1]（模式串的前 j 个字符）最长的相同前缀和后缀的长度。另外，从算法实现角度，统一令next[0] = -1。
以模式串“ABCDABD”为例，其next数组如下图所示：
KMP算法过程
这里以主串S = "A B C D A B C D A B D"和模式串P = "A B C D A B D"为例，其主要思想就是当出现不匹配情况时不进行模式串的从头匹配，而是查next数组从模式串的指定位置继续匹配，重复利用已有信息。
KMP算法的时间复杂度为O(n+m)，n是主串S的长度，m是模式串P的长度，空间复杂度是O(m),m是模式串P的长度。
需要注意的是：
- 由于子串统计是要求模式串在主串中出现的次数，这里在完成一次匹配后仍继续KMP流程。
- 这里如果要返回具体匹配起始位置也是可以在计算过程中记录的。
代码如下：
public static int kmpStringCount(String s, String p) {
// 生成next数组
int[] next = genNextArray(p);
int len_s = s.length();
int len_p = p.length();
int i = 0, j = 0;
int temp;
int count = 0;
while (i < len_s && j < len_p) {
if (s.charAt(i) == p.charAt(j)) {
i++;
j++;
} else {
temp = next[j];
if (temp == -1) {
j = 0;
i++;
} else {
j = temp;
}
}
if (j == len_p) {
count += 1;
j = next[j];
i += 1;
}
}
return count;
}
/**
* 计算next数组
*/
public static int[] genNextArray(String p) {
int length = p.length();
int[] next = new int[length + 1];
next[0] = -1;
for (int i=1; i<=length; i++) {
next[i] = calcNextVal(p.substring(0, i));
}
return next;
}
/**
* 计算next值
*/
public static int calcNextVal(String str) {
int length = str.length();
for (int i=length-1; i>=0; i --) {
String prefix = str.substring(0, i+1);
String suffix = str.substring(length-i-1);
if (prefix.equals(suffix)) {
return i;
}
}
return 0;
}
各位看官,觉得总结的有点用的，点个赞呗~ 参考文献：
