【算法】BF、KMP算法及OJ题

BF算法

为什么要先来说BF算法❓

• BF算法可以说是KMP算法的基础，KMP算法是建立在BF算法之上的。所以学习BF算法之后能够让我们更快的去理解KMP算法内容，所以我们就先BF算法说起。

什么是BF算法❓

BF算法，即暴力(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。

对于BF算法而言，如果匹配到不相等的，则模式串T要回到第一个字符。而KMP则会通过next数组回退到特定的位置。后面会展开说明。

通过上面的BF概念我们可能会一脸懵逼，我们可以通过举例子来进行理解：

假定我们给出字符串**”ababcabcdabcde”作为主串， 然后给出子串”abcd”**,现在我们需要查找子串是否在主串中出现，出现返回主串中的第一个匹配的下标，失败返回-1:

只要在匹配的过程当中，匹配失败，那么：i回退到（或者说成回溯）刚刚位置的下一个,j回退到0下标重新开始,如此往复，直到最终找到或者找不到：

基于此，我们对BF算法有了大致的理解，下面我们再来了解BF算法的另一个重要的点——回溯。

BF算法的核心

回溯：什么时候要进行回溯操作❓在主串中的元素和子串中的元素发生不匹配的情况时要进行回溯操作，回溯操作是针对于主串来说的， 我们还以上图来进行解释，此时我们的主串中的的a与子串中的c发生了不匹配的操作，满足了回溯的条件，那么我们此时的主串就要进行回溯操作。

回溯操作有一个公式：i=i-j+2。怎么去理解这个核心的公式❓这里的i和j初始化都是1，不是下标

我们将 i-j+2 分解为 （i -j +1) + 1,
i-j+1代表什么？代表主串的 i 位置前已经有 i-j+1个字符被匹配上了（也就是目前为止符合条件的最长的子串的长度），然而现在第 i 个字符匹配不上，自然就要回溯，那么就先回溯 i -j + 1个字符（本来我们的i就已经指向了1），等同于回到本次匹配的起点，然后我们再 + 1，就开始了下一次的匹配，（如果不+1就开始匹配，那不就是重复上一次的匹配过程了吗？使主串的位置++，从而找到一个新的位置再次进行匹配操作），这种回溯也决定了此算法的低效，因此也就引出了后面的KMP算法。这就是这个公式的由来。

BF代码实现

注意这里我们的下标是从0开始的。所以回溯的时候主串下标i = i-j+1即可。i=i-j+1（i现在的位置减去字符串中已经比较了j个字符就等于本次的开始位置，在加一即为第二位）

#include <stdio.h>
#include <assert.h>
#include <string.h>

//str代表主串
//sub代表子串
//返回值：返回子串在主串中的下标。如果不存在返回-1
int BF(char* str, char* sub)
{
	assert(str!=NULL && sub!=NULL);
	if (str == NULL || sub == NULL)
	{
		return -1;
	}
	int lenStr = strlen(str);
	int lenSub = strlen(sub);

	int i = 0;
	int j = 0;
	while (i < lenStr && j < lenSub)
	{
		if (str[i] == sub[j])
		{
			i++;
			j++;
		}
		else
		{
			//匹配不成功进行回溯
			i = i - j + 1;
			j = 0;
		}
	}
	if (j >= lenSub)//j走完了子串，找到了
	{
		return i - j;
	}
	return -1;
}
int main()
{
	printf("%d\n", BF("ababcabcdabcde", "abcd"));//5
	printf("%d\n", BF("ababcabcdabcde", "abcdf"));//-1
	printf("%d\n", BF("ababcabcdabcde", "ab"));//0
	return 0;
}

时间复杂度分析：最坏为O(m*n); m是主串长度，n是子串长度

KMP算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) [1] 。 来自-------百度百科。

好的，我也看不太懂，我们可以简单理解为：

与BF算法进行区别：KMP 和 BF 唯一不一样的地方在，我主串的 i 并不会回退，并且 j 也不会移动到 0 号位置，移动到特定的位置，而这个特定的位置就是该位置上next数组中存储子串要移动位置的下标

next数组的引入

首先举例，为什么主串位置i不回退❓我们需要一个特定的例子来说明这个问题：

另一个问题：子串j该如何回退？同样的，先来看一个例子：

Next数组的引入：

KMP 的精髓就是 next 数组：也就是用 next[j] = k;简单理解就是：来保存子串某个位置匹配失败后，回退的位置。

不同的 j 来对应一个 K 值， 这个 K 就是你将来要移动的 j要移动的位置。

而 K 的值是这样求的 ：

1、规则：找到匹配成功部分的两个相等的真子串（不包含本身），一个以下标 0 字符开始，另一个以 j-1 下标
字符结尾。
2、不管什么数据 next[0] = -1;next[1] = 0;在这里，我们以下标来开始，而说到的第几个第几个是从 1 开始；

看到这里，你可能还是懵的，对于K是如何求的还是不理解，我们通过两个练习来求K.你就知道是怎么求的了

练习 1： 举例对于”ababcabcdabcde”， 求其的 next 数组？

练习 2： 再对”abcabcabcabcdabcde”,求其的 next 数组？

到这里大家对如何求next数组应该问题不大了.

接下来的问题就是，已知next[i] = k;怎么求next[i+1] = ❓

如果我们能够通过 next[i]的值,通过一系列转换得到 next[i+1]得值，那么我们就能够实现这部分。

首先假设： next[i] = k 成立，那么，就有这个式子成立:P[0]…P[k-1] = P[x]…P[i-1]看个图就知道什么意思了：

得到： P[0]…P[k-1] = P[i-k]…P[i-1];这个有什么用？往下面继续看👇

到这一步：我们再假设如果 P[k] = P[i]; 我们就可以得到P[0]…P[k] = P[i-k]…P[i];那这个就是 next[i+1] = k+1，

为什么❓

接下去问题又来了：如果那么： P[k] != P[i] 呢,next[i+1] = ?

做法就是K一直回退，找到P[i]==p[k]的情况

至此，KMP的算法的思想到这里大部分结束。下面，我们通过代码来进行实现：

KMP代码实现

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>

//str是主串
//sub是子串
//pos从子串的pos位置开始找

void GetNext(char* sub, int *next,int lensub)
{
	next[0] = -1;//第一个默认为-1
	next[1] = 0;//第二个默认为0
	int i = 2;//当前i的下标，从2开始
	int k = 0;//前一项的K，k从0开始
	while(i < lensub)
	{
		if (k==-1||sub[i-1] == sub[k])
		{
			next[i] = k + 1;
			i++;
			k++;
		}
		else
		{
			k = next[k];
		}
	}
}

int KMP(char* str, char* sub, int pos)
{
	assert(str != NULL && sub != NULL);
	int lenstr = strlen(str);
	int lensub = strlen(sub);
	if (lenstr == 0 || lensub == 0) return -1;
	if (pos < 0 || pos >= lenstr) return -1;
	int i = pos;
	int j = 0;
	int* next = (int*)malloc(sizeof(int) * lensub);
	if (next == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	GetNext(sub, next,lensub);
	while (i < lenstr && j < lensub)
	{
        //j=-1的情况记得拿出来，防止越界。可能第一次就匹配失败变成了-1
		if (j==-1||str[i] == sub[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if (j >= lensub)
	{
		return i - j;
	}
	return -1;
}

int main()
{
	printf("%d\n", KMP("ababcabcdabcde", "abcd",0));//5
	printf("%d\n", KMP("ababcabcdabcde", "abcdf",0));//-1
	printf("%d\n", KMP("ababcabcdabcde", "ab",0));//0
	return 0;
}

next数组的优化

next 数组的优化，即如何得到 nextval 数组：有如下串： aaaaaaaab,他的 next 数组是-1,0,1,2,3,4,5,6,7.而修正后的数组 nextval 是：
-1， -1， -1， -1， -1， -1， -1， -1， 7。为什么出现修正后的数组，假设在 5 号处失败了，那退一步还是a，还是相等，接着退还是 a。

练习：模式串 t=‘abcaabbcabcaabdab’ ，该模式串的 next 数组的值为（ D ） ， nextval 数组的值为 （F）
。
A． 0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B． 0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2
C． 0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D． 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2
E． 0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F． 0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1

这里的选项默认从0开始，直接加1即可找出选项答案。

相关OJ题

实现 strStr()

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

废话不多说，直接上手代码：

void GetNext(char* sub, int *next,int lensub)
{
    next[0] = -1;
    next[1] = 0;
    int i = 2;
    int k = 0;
    while(i<lensub)
    {
        if(k==-1||sub[i-1]==sub[k])
        {
            next[i] = k+1;
            i++;
            k++;
        }
        else
        {
            k = next[k];
        }
    }

}
int strStr(char * haystack, char * needle){
    assert(haystack!=NULL&&needle!=NULL);
    int lenstr = strlen(haystack);
    int lensub = strlen(needle);
    if(lenstr==0||lensub==0) return -1;
    int i = 0;
    int j = 0;
    int*next = (int*)malloc(sizeof(int)*(lensub+2));
    if(next == NULL)
    {
        exit(-1);
    }
    GetNext(needle, next,lensub);
    while(i<lenstr&&j<lensub)
    {
        if(j==-1||haystack[i] == needle[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    if(j>=lensub)
    {
        return i-j;
    }
    return -1;
}