数据结构（C语言）BF+KMP 代码

笔试重点题目
BF算法,朴素查找算法
在主串str的pos位置查找子串sub,找到返回下标,没有找到返回-1
思想:相等则继续,不相等则回退;i回退到刚才的位置加1,j回退到0;
时间复杂度:O(n*m)

#include 
#include 
#include 
#include 
int  BF(const char* str, const char* sub, int pos)
{
	assert(str != NULL && sub != NULL);
	if (str == NULL || sub == NULL || pos<0 || pos>strlen(str))
	{
		return -1;
	}
	int i = pos;
	int j = 0;
	int lenstr = strlen(str);
	int lensub = strlen(sub);
	while (i < lenstr && j < lensub)//需要比较
	{
		if (str[i] == sub[j])//相等往后比较
		{
			i++;
			j++;
		}
		else//不相等,i回退到刚才的位置的下一个,j回退到0;
		{
			i = i - j + 1;
			j = 0;
		}
	}
	//利用子串是否遍历完成来判断是否查找成功
	//注意:不能利用主串来判断.
	if (j >= lensub)
	{
		return i - j;
	}
	else
	{
		return -1;
	}
}

测试BF算法

int main()
{
	const char* str1 = "ababcabcdabcde";
	const char* str2 = "abcd";
	printf("%d ", BF(str1, str2, 10));

	return 0;
}

面试的重点题目
KMP算法,i不回退,j退到K
时间复杂度:O(n+m)

#include 
#include 
#include 
#include 
#include 

static int* GetNext(const char* str)
{
	int len = strlen(str);
	int* next = (int*)malloc(len * sizeof(int));
	next[0] = -1;
	next[1] = 0;//j=1,k=0
	//找到next数组的规律
	int j = 1;
	int k = 0;
	while (j + 1 < len)
	{
		if ((k == -1) || str[k] == str[j])
		{
			next[++j] = ++k;
			
		}
		else
		{
			k = next[k];
		}
	}
	return next;
}

int  KMP(const char* str, const char* sub, int pos)
{
	assert(str != NULL && sub != NULL);
	if (str == NULL || sub == NULL || pos<0 || pos>strlen(str))
	{
		return -1;
	}
	int i = pos;
	int j = 0;
	int lenstr = strlen(str);
	int lensub = strlen(sub);

	int* next = GetNext(sub);

	while (i < lenstr && j < lensub)//需要比较
	{
		if ((j == -1) || str[i] == sub[j])//相等往后比较
		{
			i++;
			j++;
		}
		else//不相等,i不回退
		{
			//i = i - j + 1;KMPi不处理
			j = next[j];
		}
	}
	free(next);
	//利用子串是否遍历完成来判断是否查找成功
	//注意:不能利用主串来判断.
	if (j >= lensub)
	{
		return i - j;
	}
	else
	{
		return -1;
	}
}

测试KMP算法

int main()
{
	const char* str1 = "ababcabcdabcde";
	const char* str2 = "abcd";
	printf("%d ", KMP(str1, str2, 10));

	return 0;
}

可以自己练一练下边这几个题，有助于更好的理解BF和KMP

a b c a b c d a b c d a b c d e a b c

a b a c d a b c a b c d e

a a b b a a b b a a b b c d

a b a a b c a c

答案：我采用的是第一个字符标-1，差值一样就是正确的

a   b  c  a  b  c  d   a   b   c   d   a   b   c   d   e   a   b   c
-1  0  0  0  1  2  3   0   1   2   3   0   1   2   3   0   0   1   2   
a   b   a   c   d   a   b    c   a   b   c   d   e
-1  0   0   1   0   0   1    2   0   1   2   0   0 
a   a   b   b  a  a   b   b   a   a   b   b  c   d
-1  0   1   0  0  1   2   3   4   5   6   7  8   0
a   b   a  a  b   c   a   c   
-1  0   0  1  1   2   0   1