KMP算法详解

一，什么是KMP算法

KMP主要应用在字符串匹配上。

KMP的主要思想是当出现字符串不匹配时，通过已知一部分之前已经匹配的内容，避免从头再去做匹配。

所以KMP算法的重点就是如何记录已经匹配的信息，也就是next 数组的实现；

二，什么是next数组

next数组也就是前缀表。

前缀表有什么用处呢，它是在字符串不匹配时，用来确定回退位置的。

那我们来举个例子：

文本串 ：ababcabfababcabd                          模式串: ababcabd

首先要知道前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，再重新匹配，此也意味着在某个字符失配时，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置。

前缀表的定义是：记录当前位置之前的字符串中，最长相同前后缀。

三，最长相同前后缀

前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

所以如模式串ababcabd

字符串为a 的最长相等前后缀为0，为ab的最长相等前后缀为0，为aba的最长相等前后缀为1

为abab的最长相等前后缀为2  为ababc的最长相等前后缀为0，为ababca的最长相等前后缀为1

为ababcab的最长相等前后缀为2  为ababcabd的最长相等前后缀为0；

所以next数组就为 0 0 1 2 0 1 2 0

那如何使用next数组呢 

四， 构建next数组

 1，初始化

定义两个指针i和j，j指向前缀起始位置，i指向后缀起始位置。

int j=0;
next[0]=j;

完整构建代码

void getNext(string s){
    int j = 0;
    next[0] = j;
    for(int i = 1; i < s.size(); i++) { // j要保证大于0，因为下面有取j-1作为数组下标的操作
        while (j > 0 && s[i] != s[j]) { // 前后缀不相同了
            j = next[j-1]; // 向前回退
        }
        if (s[i] == s[j]) { // 找到相同的前后缀
            j++;
        }
        next[i] = j; // 将j（前缀的长度）赋给next[i]
    }
}

五，完整代码实现

#include<bits/stdc++.h>
#define MAX 10000
using namespace std;
int next[MAX];
void creat(string s)
{
	int j=0;
	next[0]=j;
	for(int i=1;i<s.size();i++)
	{
		while(j>0&&s[i]!=s[j])
		{
			j=next[j-1];
		}
		if(s[i]==s[j])
		{
			j++;
		}
		next[i]=j;
	}
}
int solve(string p,string s)
{
	int j=0;
	for(int i=0;i<p.size();i++)
	{
		while(j>0&&p[i]!=s[j])   // 不匹配
		{
			j=next[j-1];    // j 寻找之前匹配的位置
		}
		if(p[i]==s[j])      // 匹配，j和i同时向后移动
		{
			j++;
		}
		if(j==s.size()-1)   // 文本串s里出现了模式串t
		{
			return (i-s.size()+1);
		}
	}
}
int main()
{
	string p,s; //p为文本串，s为模式串 
	cin>>p>>s;
	creat(s);
	cout<<solve(p,s)<<endl;   
	return 0;
}