这两天复习数据结构（严蔚敏版），记录第四章串中的两个重要算法，BF算法和KMP算法，博主主要学习Java，所以分析采用Java语言，后面会补上C语言的实现过程。
1、Brute-Force算法（暴力法）
要求：将主串的第i个字符（一般情况i为1）和字串的第一个字符进行比较。若相等，则继续比较后续字符；若不相等，则从主串的下一个字符起，重新与子串的第一个字符比较。成功，返回主串中与子串相匹配的子序列的第一个字符的序号；失败，返回0
public class Brute_Force {
/**
* 暴力法 ,O(m*n) (m、n分别为主串长度和子串长度)
* @param S 主串（原始字符串）
* @param T 子串（模式字符串）
* @return 如果模式字符串在原始字符串中存在，返回模式字符串在原始字符串中第一次出现的索引
*/
private int Index_BF(String S, String T) {
//习惯性排除错误的模式
if (S==null || S.length()<=0 || T==null || T.length()<=0)
return 0;
int S_length = S.length();
int T_length = T.length();
int i=0, j=0;
while (i<S_length && j<T_length) {
if (S.charAt(i) == T.charAt(j)) {
i++;
j++;
}else {
//不等
i = i-j+1; //这一步的思想是主串返回到的步数为子串移动的步数i-j，然后从下一个开始+1
j = 0; //j返回索引为0的位置
}
}
if (j == T_length) {
return i-T_length;
}
return 0;
}
//主方法，测试
public static void main(String[] args) {
Brute_Force bf = new Brute_Force();
String S = "hello world";
String T = "world";
System.out.println(bf.Index_BF(S,T)); //6
}
}
2、KMP算法
要求效果同上，只是更合理地应用部分已经匹配的结果
public class KMP {
/**
* KMP 高效法 ,O(m+n) (m、n分别为主串长度和子串长度)
* @param S 主串（原始字符串）
* @param T 子串（模式字符串）
* @return 如果模式字符串在原始字符串中存在，返回模式字符串在原始字符串中第一次出现的索引
*/
private int Index_KMP(String S, String T) {
//习惯性排除错误的模式
if (S==null || S.length()<=0 || T==null || T.length()<=0)
return 0;
//得到子串的next数组
int[] nextArr = getNextArray(T);
int S_length = S.length();
int T_length = T.length();
int i=0, j=0;
while (i<S_length && j<T_length) {
if (j==-1 || S.charAt(i) == T.charAt(j)) {//j==-1第一个字符就和当前测试的字符不相等
i++;
j++;
}else {
j = nextArr[j];
}
}
if (j==T_length) {
return i-T_length;
}
return 0;
}
/**
* 获取模式字符串的next数组
* @param str 子串
* @return
*/
private int[] getNextArray(String str) {
//习惯性排除错误的模式
if (str==null || str.length()<=0)
return null;
int length = str.length();
int[] nextArr = new int[length];
int j=0, k=-1;
nextArr[0] = -1;
while (j<length-1) {
if (k==-1 || str.charAt(j) == str.charAt(k)) {
j++;
k++;
nextArr[j] = k;
}else {
k = nextArr[k];
}
}
return nextArr;
}
//主方法，测试
public static void main(String[] args) {
KMP kmp = new KMP();
String S = "hello world";
String T = "world";
System.out.println(kmp.Index_KMP(S,T)); //6
}
}
3、KMP的讲解
KMP算法的核心，通俗来讲是，当S[i]和T[j]发生不匹配现象时，i指针不需要回溯，只需j指针回溯即可。详情可以看下这篇知乎：
https://www.zhihu.com/question/21923021/answer/281346746
大体的对比：
4、C语言实现
考试还是要用C语言，还是得好好参考下
BF算法：
#include <stdio.h>
#include <string.h>
//串普通模式匹配算法的实现函数，其中 B是主串，A是子串
int BF(char * B,char *A){
int i=0,j=0;
while (i<strlen(B) && j<strlen(A)) {
if (B[i]==A[j]) {
i++;
j++;
}else{
i=i-j+1;
j=0;
}
}
//跳出循环有两种可能，i=strlen(B)说明已经遍历完主串，匹配失败；j=strlen(A),说明子串遍历完成，在主串中成功匹配
if (j==strlen(A)) {
return i-strlen(A)+1;
}
//运行到此，为i==strlen(B)的情况
return 0;
}
int main() {
int number = BF("hello world", "world");
printf("%d",number);
return 0;
}
KMP算法：
#include <stdio.h>
#include <string.h>
void Next(char*T,int *next){
int i=1;
next[1]=0;
int j=0;
while (i<strlen(T)) {
if (j==0||T[i-1]==T[j-1]) {
i++;
j++;
next[i]=j;
}else{
j=next[j];
}
}
}
int KMP(char * S,char * T){
int next[10];
Next(T,next);//根据模式串T,初始化next数组
int i=1;
int j=1;
while (i<=strlen(S)&&j<=strlen(T)) {
//j==0:代表模式串的第一个字符就和当前测试的字符不相等；S[i-1]==T[j-1],如果对应位置字符相等，两种情况下，指向当前测试的两个指针下标i和j都向后移
if (j==0 || S[i-1]==T[j-1]) {
i++;
j++;
}
else{
j=next[j];//如果测试的两个字符不相等，i不动，j变为当前测试字符串的next值
}
}
if (j>strlen(T)) {//如果条件为真，说明匹配成功
return i-(int)strlen(T);
}
return -1;
}
int main() {
int i=KMP("hello world","world");
printf("%d",i);
return 0;
}