KMP算法笔记

心已赠人 2022-08-14 00:47 137阅读 0赞

Kmp算法我是看July博客学习，这里只是做个笔记，详细内容见July的blog: [ http://blog.csdn.net/v\_july\_v/article/details/7041827][http_blog.csdn.net_v_july_v_article_details_7041827]

Kmp算法的用途：有一个文本串S和一个模式串P,现在要查找P在S中的位置。暴力匹配算法需要对文本串S进行回溯，kmp算法就是让文本串不回退，只需要移动模式串j即可。

**Kmp算法大体思想：**就是当s\[i\]==p\[j\]时，我们对i++，j++；如果不相等则令j=next\[j\]。这里next\[j\]为j字符之前的字符串中有多大长度的相同前缀后缀（注意前缀不能包含最后一个，同时后缀不能包含第一个，所以aaaab的next数组为-10123）。相当于将模式串向右移动了j-next\[j\]位。Next数组的求解采用的是迭代的思想，需要分p\[j\]是否等于p\[k\]两种情况以求得next\[j+1\]。

**时间复杂度：**暴力匹配算法的时间复杂度为O(n\*m)(最差的情况). Kmp算法的时间复杂度为O(n+m)， 因为match串(模式串)最多向右推动了长度就为n,而字符串本身不回退。这里n和m分别为文本串和字符串的长度。next时间复杂度为O(M)，可以这样理解：循环中有两个变量，j和k,而j与j-k每次都是增加的或者一个不变，故最多循环2M次，时间复杂度为O(M)

**Next数组求解**：next\[0\]=-1，k=-1; next数组通过代码递推求得，假定next\[j\] = k求next\[j+1\]，先判断p\[j\]是否等于p\[k\], 如果相等则令next\[++j\] =++k; 否则令k=next\[k\]<这个不太好理解>继续迭代。时间复杂度为O(m).

k=next\[k\]；为什么不是k--？给个例子DADCDADDE, 当求E的next值时就会出错。k=k-1的话求到的是倒数第二个D，则为next\[E\]=2+1=3这里是DAD明显不对，然后再看ABDABCABDABDE据对称性得k=next\[k\]是正确的

**优化next数组：**next数组主要针对模式串abab的情况，比如在文本串abacab中寻找，此时当p\[3\]与s\[3\]匹配失败时，则将abab向右移动两位，此时p\[1\]仍然等于b，匹配必然失败，优化的next数组主要解决这个问题。当p\[3\]=p\[next\[3\]\]时 令next\[3\]=next\[next\[3\]\]。看代码则很好理解了。

**以上则是个人理解笔记，下面给出具体代码：**

1：kmp算法代码

#include <iostream>
    using namespace std;
    
    // 获取next数组
    void getNext(int *next, const char *p)        // 已知next[j] 求next[j+1] 分p[j]是否等于p[k]两种情况 迭代的思想
    {
    	next[0] = -1;
    	int k = -1;
    	int j = 0;
    	while(j < strlen(p)-1)
    	{
    		if(k == -1 || p[j] == p[k])
    		{
    			k++;
    			j++;
    			next[j] = k;
    		}
    		else{
    			k = next[k];      //   继续迭代
    		}
    	}
    }
    
    // 获取优化next数组
    void getNextOpt(int *next, const char *p)        // 已知next[j] 求next[j+1] 分p[j]是否等于p[k]两种情况 迭代的思想
    {
    	next[0] = -1;
    	int k = -1;
    	int j = 0;
    	while(j < strlen(p)-1)
    	{
    		if(k == -1 || p[j] == p[k])
    		{
    			k++;
    			j++;
    			if(p[j] != p[k])    //  对next数组进行优化 以对abab 这样的不需要进行重复
    				next[j] = k;
    			else next[j] = next[k];
    		}
    		else{
    			k = next[k];      //   
    		}
    	}
    }
    
    // kmp 算法
    int kmpSearch(const char *p, const char*s)
    {
    	int ptrLen = strlen(p);     //  获取模式串和文本串的长度
    	int strLen = strlen(s);
    	int *next = new int[ptrLen];    // 动态申请next数组
    	getNext(next, p);          //  获取next数组
    
    	int i = 0, j = 0;
    	while(i < strLen && j < ptrLen){      
    		if(j == -1 || s[i] == p[j])
    		{
    			i++;
    			j++;
    		}
    		else if(j == 0)              // 这样对于首字符不满足的时候直接优化
    			i++;
    		else{
    			j = next[j];
    		}
    	}
    
    	delete[] next;   // 释放动态申请的数组
    	if(j == ptrLen)
    		return i - j;
    	else return -1;
    	
    }
    int main(){
    
    	char *ptr = "abcd";
    	char *str = "abababcd";
    	cout << kmpSearch(ptr, str) << endl;
    	return 0;
    }

2：暴力匹配算法——又被称为朴素字符串匹配算法(Naive string match)

#include <iostream>
    using namespace std;
    
    int violenceSearch(const char *p, const char *s)
    {
    	int ptrLen = strlen(p);     //  获取模式串和文本串的长度
    	int strLen = strlen(s);
    
    	int i = 0, j = 0;
    	while(i < strLen && j < ptrLen){      
    		if(s[i] == p[j])
    		{
    			i++;
    			j++;
    		}
    		else{
    			i = i-j+1;
    			j = 0;
    		}
    	}
    	if(j == ptrLen)
    		return i - j;
    	else return -1;
    }
    
    
    int main(){
    	char ptr[100];
    	char str[100];
    	cin >> ptr >> str;
    	cout << violenceSearch(ptr, str) << endl;
    	
    }

3：求最大长度表算法

也可以由最大长度表来求next数组，通过最大长度表各项向右移动一位，然后初值赋值-1即可，但是这种方法求最大长度表所消耗的时间为O(n^2)

//  针对一个字符串获得最大长度的相同前缀后缀
    int getMaxFix(const char *p, int pLen)
    {
    	int k =pLen/2;
    	while(k > 0)
    	{
    		//bool flag = false;
    		int i = 0, j = pLen -k;
    		while(i < k)
    		{
    			if(p[i] == p[j])
    			{
    				i++;
    				j++;
    			}
    			else{
    				//flag = true;
    				k--;
    				break;
    			} 
    		}
    	}
    	return k;
    }
    
    
    //  获得最大长度表
    void getMaxTable(const char *p, int *table)
    {
    	for(int i = 0; i < strlen(p); i++)
    	{
    		table[i] = getMaxFix(p, i+1);
    	}
    }

**KMP算法的变形**

这是hihoCoder1015的题目。题目地址：[http://hihocoder.com/problemset/problem/1015][http_hihocoder.com_problemset_problem_1015]

即求模式串在文本串中出现的次数。这里算法的基本思想就是求出模式串的公共前缀后缀即next\[s.size()\]，当j==s.size()的时候让j=next\[s.size()\]就可以了。就好比模式串ABCDEA，当结束的时候j=6，此时next\[j\] = 1,故让j=1继续去匹配，即前面有k位和字符串中是相同的。

代码如下：

#include <iostream>
    #include <string>
    using namespace std;
    #define PMAXSIZE 10010
    
    
    void getNext(int *iNext, const string s){
    	int j = 0, k = -1;
    	iNext[0] = -1;
    	string p = s+"#";
    	while(j < p.size()-1){
    		if(k == -1 || p[j] == p[k]){
    			j++;
    			k++;
    			if(p[j] != p[k])iNext[j] = k;
    			else iNext[j] = iNext[k];
    		}
    		else k = iNext[k];
    	}
    }
    int kmpAlg(const string &p, const string &s){
    	int i = 0, j = 0;
    	int count = 0;
    	int *iNext = new int[p.size()+1];
    	getNext(iNext, p);
    	while(i < s.size()){
    		if(j == -1 || s[i] == p[j]){
    			i++;
    			j++;
    		}else if(j == 0)
    			i++;
    		else
    			j = iNext[j];
    		if(j == p.size()){
    			count++;
    			j = iNext[j];
    		}
    	}
    	delete []iNext;
    	return count;
    }
    
    
    /*
     //freopen是被包含于C标准库头文件<stdio.h>中的一个函数，用于重定向输入输出流。
     该函数可以在不改变代码原貌的情况下改变输入输出环境，但使用时应当保证流是可靠的。
    */
    int main(){
    	int N;
    #define KMP1015
    #ifndef KMP1015
    	freopen("input.txt", "r", stdin);  
    #endif
    	cin >> N;
    	while(N--){
    		string p, s;
    		cin >> p >> s;
    		cout << kmpAlg(p, s) << endl;
    	}
    	return 0;
    }
    
    /*
    input:
    5
    HA
    HAHAHA
    WQN
    WQN
    ADA
    ADADADA
    BABABB
    BABABABABABABABABB
    DAD
    ADDAADAADDAAADAAD
    
    output:
    3
    1
    3
    1
    0
    */

参考文献：http://blog.csdn.net/v\_july\_v/article/details/7041827

作者：小村长 出处：[http://blog.csdn.net/lu597203933][http_blog.csdn.net_lu597203933] 欢迎转载或分享，但请务必声明文章出处。 （新浪微博：小村长zack, 欢迎交流！

[http_blog.csdn.net_v_july_v_article_details_7041827]: http://blog.csdn.net/v_july_v/article/details/7041827
[http_hihocoder.com_problemset_problem_1015]: http://hihocoder.com/problemset/problem/1015
[http_blog.csdn.net_lu597203933]: http://blog.csdn.net/lu597203933