03

(13条消息) 从头到尾彻底理解KMP（2014年8月22日版）_v_JULY_v的博客-CSDN博客_从头到尾彻底理解kmp

代码随想录 (programmercarl.com)

(13条消息) 数据结构KMP算法配图详解（超详细）_哈顿之光的博客-CSDN博客_数据结构kmp算法

从该博客学习到的知识，便于以后复习使用，记录下来，我觉得KMP算法的核心思想就是利用对称的思想。

一、什么是KMP算法

二、next[ ] 数组表示什么

三、前缀表和next[  ]之间的关系，为什么要用前缀表

四、最长相等前后缀

五、next[ ] 数组构造

六、KMP算法的优化

七、力扣28题

一、什么是是KMP算法

        KMP算法用于解决在暴力匹配算法，当字符串不匹配时，模式串要重头进行重新匹配的问题，KMP算法的重要思想是：当出现字符串不匹配时，可以记录之前一部分匹配的内容，利用这些信息避免重头匹配问题。

二、next[ ] 数组表示什么

        next[ ] 数组表示当前字符之前的字符串中，有最大长度相同的前缀和后缀，例如：next[j]=k代表j位置之前的字符串中，有最大长度为k的相同前缀和后缀。

三、前缀表和next[ ]之间的关系，为什么要用前缀表

        next[ ] 数可以表示一个前缀表，前缀表：前缀表是用来回退的，它记录了模式串与主串不匹配时，模式串应该从哪个位置重新开始匹配。next数组可以是前缀表向右移动一位，也可以是前缀表值-1。

        用前缀表的原因是：因为前缀表找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面从新匹配就可以了，所以前缀表具有告诉我们当前位置匹配失败，跳到之前已经匹配过的地方的能力。

四、最长相等前后缀（例如模式串：aabbaca）

（1）前缀：不包含最后一个字符且以首字符开头的连续子串。

        前缀有:a aa aab aabb aabba aabbac

（2）后缀：不包含开头字符且以最后一个字符结尾的连续子串。

        后缀有: a ca aca baca bbaca abbaca

（3）最长相等前后缀：前缀子串和后缀子串相等时候的最大长度。

所以举个例子：a的最长相等前后缀为0，aa的最长相等的前后缀为1，aaa的最长相等的前后缀长度为2。

五、next数组的构造

（1）对前缀表不做 *** 作处理

        ①初始化

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

然后还要对next数组进行初始化赋值，如下：

int i = 0;
next[0]=i //要始终记住next就是前缀表的长度

        ②处理前后缀不相同的情况

        ③处理前后缀相同的情况

        ④确定前缀长度

前缀表不移动的情况

void getNextval(string s,int next[]){
        next[0] = 0;
        int i = 0;
        for(int j = 1;j < s.size(); j++){//注意从1开始
            while(i > 0 && s[i] != s[j]) {//前后缀不相同了
//如果s[i]与s[j]不相同，就要找i前一个元素在next数组的值就是回退
                i = next[i - 1];//向前回退
            }
            if(s[i] == s[j]) { //找到相同的前后缀
                i++;
            }
            next[j] = i;//将i（前缀长度)赋给next【j】
        }
    }

（2）将前缀表右移一位

typedef struct
{	
	char data[MaxSize];
	int length;			//串长
} SqString;
//SqString 是串的数据结构
//typedef重命名结构体变量，可以用SqString t定义一个结构体。
void GetNext(SqString t,int next[])		//由模式串t求出next值
{
	int j,k;
	j=0;k=-1;
	next[0]=-1;//第一个字符前无字符串，给值-1
	while (j

void GetNext(char* p,int next[])
{
	int pLen = strlen(p);
	next[0] = -1;
	int k = -1;
	int j = 0;
	while (j < pLen - 1)
	{
		//p[k]表示前缀，p[j]表示后缀
		if (k == -1 || p[j] == p[k]) 
		{
			++k;
			++j;
			next[j] = k;
		}
		else 
		{
			k = next[k];
		}
	}
}

//优化过后的next 数组求法
void GetNextval(char* p, int next[])
{
	int pLen = strlen(p);
	next[0] = -1;
	int k = -1;//k表示前缀末尾的位置
	int j = 0;//j表示后缀末尾位置
	while (j < pLen - 1)
	{
		//p[k]表示前缀，p[j]表示后缀  
		if (k == -1 || p[j] == p[k])
		{
			++j;
			++k;
			//较之前next数组求法，改动在下面4行
			if (p[j] != p[k])
				next[j] = k;   //之前只有这一行
			else
				//因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
				next[j] = next[k];
		}
		else
		{
			k = next[k];
		}
	}
}

class Solution {
public:
    void getNext(string needle,int next[]){
        int i=-1;
        int j=0;
        next[0]=-1;
        while(j(haystack.size())&&j(needle.size())){
            if(j==-1||haystack[i]==needle[j]){
                ++i;
                ++j;
            }else{
                j=next[j];
            }
        }
        if(j>=needle.size()) return i-needle.size();
        else return-1;
        //普通方法实现串的模式匹配问题
        // int i=0,j=0;
        // if(haystack.size()

class Solution {
public:
    void getNextval(string s,int next[]){
        next[0] = 0;
        int i = 0;
        for(int j = 1;j < s.size(); j++){
            while(i > 0 && s[i] != s[j]) {
                i = next[i - 1];
            }
            if(s[i] == s[j]) {
                i++;
            }
            next[j] = i;
        }
    }
    bool repeatedSubstringPattern(string s) {
        //s=s+'a';
        int slen=s.size();
        if(slen==1) return false;
        int next[slen];
        getNextval(s,next);
        if(next[slen-1]!=0&&slen%(slen-next[slen-1])==0) return true;
        else return false;
    }
};