数据结构实现—字符串模式匹配（KMP算法，CC++）

数据结构实现—字符串模式匹配（KMP算法，C/C++）

1. ​ 实现字符串的数组存储。
2. ​ 实现串的朴素的匹配算法，找出子串位置
3. ​ 编写改进型的串的匹配算法，指出改进在何处，时间复杂度和空间复杂度各是多少。

需求分析

朴素算法会造成大量的回溯匹配，从而运行效率会很低，我们的需求就是减少不必要的回溯从而使得效率进一步提升。程序中的sample函数实现的是字符串的朴素模式匹配，get_next函数的作用是得到每次匹配失败后子串的最佳回溯位置，KMP实现字符串的模式匹配

概要说明

字符串匹配优化采用了KMP算法，先举个例子

char *str = “bacbababadababacambabacaddababacasdsd”;

char *ptr = “ababaca”;12

str有两处包含ptr 分别在str的下标10，26处包含ptr。

一般匹配字符串时，我们从目标字符串str（假设长度为n）的第一个下标选取和ptr长度（长度为m）一样的子字符串进行比较，如果一样，就返回开始处的下标值，不一样，选取str下一个下标，同样选取长度为n的字符串进行比较，直到str的末尾（实际比较时，下标移动到n-m）。这样的时间复杂度是O(n*m)。

KMP算法：可以实现复杂度为O(m+n)

如何简化了时间复杂度： 充分利用了目标字符串ptr的性质（比如里面部分字符串的重复性，即使不存在重复字段，在比较时，实现最大的移动量）。

详细设计

依旧是上面的例子

看目标字符串ptr： ababaca 这里我们要计算一个长度为m的转移函数next。

next数组的含义就是一个固定字符串的最长前缀和最长后缀相同的长度。

比如：abcjkdabc，那么这个数组的最长前缀和最长后缀相同必然是abc。 cbcbc，最长前缀和最长后缀相同是cbc。 abcbc，最长前缀和最长后缀相同是不存在的。

注意最长前缀：是说以第一个字符开始，但是不包含最后一个字符。 比如aaaa相同的最长前缀和最长后缀是aaa。 对于目标字符串ptr，ababaca，长度是7，所以next[0]，next[1]，next[2]，next[3]，next[4]，next[5]，next[6]分别计算的是 a，ab，aba，abab，ababa，ababac，ababaca的相同的最长前缀和最长后缀的长度。由于a，ab，aba，abab，ababa，ababac，ababaca的相同的最长前缀和最长后缀是“”，“”，“a”，“ab”，“aba”，“”，“a”,所以next数组的值是[-1,-1,0,1,2,-1,0]，这里-1表示不存在，0表示存在长度为1，2表示存在长度为3。这是为了和代码相对应。

接下来的流程就是一个循环过程了。事实上，每一个字符前的字符串都有最长相等前后缀，而且最长相等前后缀的长度是我们移位的关键，所以我们单独用一个next数组存储子串的最长相等前后缀的长度。而且next数组的数值只与子串本身有关。 总结一下，next数组作用有两个： 一是

next[i]的值表示下标为i的字符前的字符串最长相等前后缀的长度。

二是：

表示该处字符不匹配时应该回溯到的字符的下标

next有这两个作用的源头是：字符串的最长相等前后缀

分析一下KMP算法的时间复杂度： KMP算法中多了一个求数组的过程，多消耗了一点点空间。我们设主串s长度为n,子串t的长度为m。求next数组时时间复杂度为O(m)，因后面匹配中主串不回溯，比较次数可记为n，所以KMP算法的总时间复杂度为O(m+n)，空间复杂度记为O(m)。相比于朴素的模式匹配时间复杂度O(m*n)，KMP算法提速是非常大的。但是我们还可以进一步优化。

看一个例子: 主串s=“aaaaabaaaaac” 子串t=“aaaaac” 这个例子中当‘b’与‘c’不匹配时应该‘b’与’c’前一位的‘a’比,这显然是不匹配的。'c’前的’a’回溯后的字符依然是‘a’。 我们知道没有必要再将‘b’与‘a’比对了，因为回溯后的字符和原字符是相同的，原字符不匹配，回溯后的字符自然不可能匹配。但是KMP算法中依然会将‘b’与回溯到的‘a’进行比对。这就是我们可以改进的地方了。我们改进后的next数组命名为：nextval数组。KMP算法的改进可以简述为： 如果a位字符与它next值指向的b位字符相等，则该a位的nextval就指向b位的nextval值，如果不等，则该a位的nextval值就是它自己a位的next值。

代码

#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int sample(char* str, char* x)
{
   int len1 = strlen(str), len2 = strlen(x);
   for (int i = 0; i < len1 - len2; i++)
   	for (int j = 0; j < len2; j++)
   		if (str[i + j] == x[j])
   		{
   			if (j == len2 - 1)
   				return i;
   		}
   		else
   			break;
   return -1;
}
void get_next(int* next, char* x)
{
   int len = strlen(x);
   int i = 0, j = -1;
   next[0] = -1;
   while (i < len - 1)//防止溢出
   {
   	if (j == -1 || x[i] == x[j])
   	{
   		i++;
   		j++;
   		if (x[i] != x[j])
   			next[i] = j;
   		else
   			next[i] = next[j];
   	}
   	else
   		j = next[j];
   }
}
int KMP(char* str, char* x)
{
   int next[1000];
   int len1 = strlen(str), len2 = strlen(x), i = 0, j = 0;
   get_next(next, x);
   while (i < len1 && j < len2)
   {
   	if (j == -1 || str[i] == x[j])
   	{
   		i++;
   		j++;
   	}
   	else
   		j = next[j];
   	if (j == len2)
   	{
   		return i-len2;
   	}
   }
   return -1;
}
int main()
{
   char str[1000], x[1000];
   scanf("%s%s", str, x);
   cout << "朴素字符串匹配：";
   cout << sample(str, x)+1 << endl;
   cout << "改进后的KMP字符串匹配：";
   cout << KMP(str, x)+1 << endl;
   return 0;
}