【算法】KMP算法

普通暴力做法与KMP的区别:

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

暴力求解：
首先我们会联想到用两个for循环镶套进行依次遍历，即是设置两个指针分别指向模式串和模板串，两个指针从左到右一个个地匹配，如果这个依次向右匹配过程中有某个字符不匹配，模板串（p）指针就跳回到第一位，模式串(s)指针向右移动一位。

#include <iostream>
using namespace std;
int n, m, t;
string s, p;//s为较长字符串（模式串）
int main()
{
	cin >> n >> p >> m >> s;
	for (int i = 0; i < m; i++)
	{
		bool flag = true;// 最开始是匹配成功的状态
		for (int j = 0; j < n; j++)
		{
			if (s[i + j] != p[j])
			{
				flag = false;//只要有一个不通过，则false
				break;
			}
		}
		if (flag == true)
		{
			cout << i << " ";
		}
	}
	return 0;
}

KMP算法求解
KMP思想：当出现字符串不匹配的情况时，可以知道一部分之前已经匹配的的文本内容，利用这些信息避免从头再去做匹配，同时比较指针不回溯，而是直接跳过一些字符串（利用next数组），使得原来模式串中的前缀直接移动到后缀位置上。（其中前缀表担负重任)
KMP运行操作图如下所示：
1.我们可以发现因为主串在到第四位的时候匹配失败，到第四位之前和主串都匹配，如果继续将主串指针右移一位的话就会不匹配。但之前因为我们已经知道前面三个字符都是匹配的，那我们就可以利用这个信息找出接下来指针该移动的位置。思路就是可以让i先不动，只需要移动j即可；

在每次失配时，不是把p串往后移一位，而是把p串往后移动至下一次可以和前面部分匹配的位置，这样就可以跳过大多数的失配步骤，从而减少运算次数降低了时间复杂度。而每次p串移动的步数就是通过查找next[ ]数组（接下来会继续介绍）确定的。

前缀：除了最后一个字符以外，该字符串的全部头部组合；
后缀：除了第一个字符以外，该字符串的全部尾部组合；

例如：ababa
其前缀为：a、ab、aba、abab；
其后缀为：a、ba、aba、baba；

部分匹配表的递推过程

next[j] = k代表p[j]之前的模式串子串中，有长度为k的相同前缀和后缀。

已知next [0, ..., j]，如何递推next [j + 1]？

对于P的前j+1个序列字符：

若p[k] == p[j]，则next[j + 1 ] = next [j] + 1 = k + 1；

证明如下：

因为P[0 ~ k-1] == p[j-k ~ j-1]。（next[j] == k）

如果P[k] == P[j]，则P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]。

即：P[0 ~ k] == P[j-k ~ j]，即next[j+1] == k + 1 == next[j] + 1。

若p[k ] ≠ p[j]，如果此时p[ next[k] ] == p[j ]，则next[ j + 1 ] = next[k] + 1，否则继续递归前缀索引k = next[k]，而后重复此过程。

#include<bits/stdc++.h>
using namespace std;
string s,t;
int slen,tlen,next[1000];
void get_next(string t){//求模式串t的next[]数组的函数 
		int j=0,k=-1;
		next[0]=-1;
		while(j<tlen){
			if(k==-1||t[j]==t[k])
				next[++j]=++k;
			else
				k=next[k];
		} 
} 
int kmp(string s,string t,int pos){
	int i=pos,j=0;
	slen=s.length();
	tlen=t.length();
	get_next(t);
	while(i<slen&&j<tlen){
		if(j==-1||s[i]==t[j])
			i++,j++;
		else
			j=next[j];
	}
	if(j>=tlen){//成功 
		return i-tlen+1;
	}else{
		return -1;
	}
}
int main(){
	cin>>s>>t;
	int ans =kmp(s,t,0);
	cout<<ans<<endl;
	return 0;
}

【算法】KMP算法

评论区