字符串匹配算法--KMP

问题提出

• 若有一问题：给定模式串P和长文本S，要求模式串P在长文本S第一次出现的位置/求出现的次数
• 例：假定P=“abcbc”，S=“abcabcbcbca”

朴素方法求解

• 若用如上图朴素的暴力算法匹配，求解模式串P在长文本第一次出现的位置（返回第一个字符的地址）：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
using namespace std;
string p, s;

int get_ans()
{
	int idx = 0;
	for (idx; idx < s.size(); idx++) //每次匹配失败只左移动一个单位
	{	
		int j = 0;
		while (idx + j < s.size() && j < p.size() &&s[idx + j] == p[j])
			j++;
		if (j == p.size()) return idx;
	}
	return -1;
}

int main()
{

	cin >> p >> s;
	cout << get_ans();
	return 0;
}

• 显而易见的，时间复杂度约为$O(nm)$，n为文本串s长，m为模式串长，显然，时间复杂度很高，算法效率低。

KMP算法背景提出

• 那有没有什么方法可以降低其时间复杂度呢？
• 显然，我们发现，在前面的算法中，前面已匹配的字符我们已经清楚是否满足匹配的，可以直接跳过重复匹配的部分，继续往后匹配。而KMP算法就是依据这种思想，避免回溯重复判断同一字符是否匹配，从而提高算法效率。
• 在这里我们需要用到的有：
  • Next[]数组，用于记录模式串p的相同字符的最长最近前缀的尾。即用于在遇到不匹配的字符时，回溯到上一个该字符出现的地方继续匹配（回溯p模式串）
  • 那么之后在匹配p和s时，遇到不匹配的即回溯到该p此时的字符的上一个出现点往后匹配。那为什么直接往左移动，回溯到上一个该字符的地方，不会导致其前面的部分的字符和S的文本串相应位置不匹配呢？因为，在Next数组预处理模式串P时，就已经确保了其回溯的部分，是否存在重复出现相同字符子串。
  • 例如：P = “abcaabc”（假设从1开始算），那么Next[] = {0, 0, 0, 1, 1, 2, 3},如第3个a，与b匹配时，不同，那么就回退到上一个匹配处，也即0号点，那么继续匹配，发现第一个a和第三个a字符相同，那么继续往后匹配，所以，回退已保证其重复与否的正确性。
    
• 附上代码解析：

// s[]是长文本，p[]是模式串， n是s的长度，m是p的长度

//求模式串的Next数组：求Next相当于自身作为p和s自我匹配。
for(int i = 2, j = 0; i <= m; i++) //从1开始下标
{
    while(j && p[i] != p[j+1]) j = ne[j];

    if(p[i] == p[j+1]) j++;
    ne[i] = j;
}

//匹配
for(int i = 1, j = 0; i <= n; i++)
{
	//若一直匹配都不成功，j会一直回溯到j=0，即从头开始匹配。
	while(j && s[i] != p[j+1]) j = ne[j];
	
    //进行上面检查操作后，匹配j+1与i成功，则j++
    if(s[i] == p[j+1]) j ++;
    
    if(j==m)
    {
        //return j-m+1;返回第一个匹配成功的下标
        j = ne[j];
        //匹配成功后的进行的相应操作
    }
}

• 模板题：AcWing:831. KMP字符串
  给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。模式串 P在字符串 S中多次作为子串出现。求出模式串 P在字符串 S中所有出现的位置的起始下标。

  • 题解：

  #include<iostream>
  using namespace std;
  const int N = 1e5 + 10;
  
  char p[N], s[N*10];
  int ne[N]; //next数组
  
  int main()
  {
  	ios::sync_with_stdio(0);
  	cin.tie(0),cout.tie(0);
  
  	int n, m;
  	cin>>n>>p>>m>>s;
  
  	//next数组预处理
  	for(int i  = 1; j = 0; i < n; i++)
  	{
  		while(j && p[i] != p[j]) j = ne[j - 1];
  		//注意，都是j-1，因为j是待匹配的，
     		//匹配失败了，就从刚才j-1，即匹配好的最后一个回退
     		if(p[i] == p[j]) j++;
     		ne[i] = j;
  	}
  	//匹配算法
  	for(int i = 0, j = 0; i < m; i++)
  	{
  		while(j&& s[i] != p[j]) j = ne[j-1];
  		if(s[i] == p[j]) j++;
  		if(j == n) 
  		{
  			j = ne[j-1];
  			cout<<i - n + 1 <<" ";
  		}
  	}
  	return 0;
  }
  

• 易知，KMP算法的时间复杂度为线性的，约为$O(m+n)$.