字符串匹配KMP算法

2017-03-28

题目:给定一个待匹配字符串和一个模板字符串,要求找到该串中模板字符串首次出现的位置,如果没有则返回-1.
第一种方法:朴素字符串匹配算法,也就是暴力枚举法,对需要匹配的字符串的每个字符进行一次匹配(在这里一次匹配操作是指两个等长字符串匹配),伪代码如下:

NAIVE_STRING_MATCHER(T,P)
n=T.length
m=P.length
for s=0 to n-m
	ifP[1..m]==T[s+1..s+m]
return s;

其中第五行的操作记为比较两个等长字符串是否相等.类似于strcmp()函数,这些都很好理解,strcmp()复杂度最高为O(L)(L为待匹配字符串长度).所以整个算法时间复杂度为O(M*N)
第二种方法:KMP算法,为了由于朴素算法每一次的不匹配只移动一个偏移量,这会导致之前的已匹配区域重复匹配,为了能确定不匹配时该移动多少偏移量从而能利用之前的信息,所以我们需要一个next数组,也就是能确定当字符不匹配时,模板字符串向右移多少偏移量(数组的值真正记录的是在该位置前缀后缀最大公共长度,也就是该位置长度减去需要的偏移量).举个例子来说:
假设字符串”ababcba”,模板字符串是”abc”,
首先 a b c b a b a 由于c和a不等(此时位置在b,我们确定的是下一个字符匹配) 于是我们只移动模板2个偏移量,继续匹配
a b a
a b c b a b a对应于next[2]=0(2-2);
a b c
所以关键就是计算next数组.
next数组计算伪代码如下:

 COMPUTE_PREFIX_FUNCITION(P)
 m=P.length
 let next[1..m] be a new array
 next[1]=0
 k=0
 for q=2 to m
 	while k>0 and P[k+1]!=P[q]
  		k=next[k]
 	if P[k+1]==P[q]
	k=k+1
next[q]=k;
 return next;

算法关键就在于第7-8行,while循环的总时间为O(m),从观察k的值开始,第一,在第5行,k初始值为0,并且增加k的唯一方法是通过第10行的递增操作,该操作在第6-11行的for循环中每次最多执行一次,因为k最多增加m-1次,第二,刚进行for循环时,k小于q,并且每次循环q都会增加,所以k永远小于q因此next[q]永远小于q,所以while循环会使q递减.所以while循环最多迭代m-1次.
下面是之前那道题的两种解法:

/*完成函数int strStr(const string& str1,const string str2)功能,找到str1中子串str2的首字符出现的位置,如果没有则返回0
 * 暴力解法O(m*n),也可以利用高效的字符串匹配算法例如KMP算法.*/
#include<iostream>
#include<string>
#include<vector>
using namespace std;
class Solution{
public:
	int strStr(const string& haystack,const string& needle){
		if(needle.empty())return 0;
		auto pos=haystack.begin();
		const int N=haystack.size()-needle.size()+1;
		for(int i=0;i<N;i++){
			int j=i;
			int k=0;
			while(j<haystack.size()&&k<needle.size()&&haystack[j]==needle[k]){
				k++;
				j++;
			}
			if(k==needle.size())
				return i;
		}
		return -1;
	}
};
/*KMP算法.时间复杂度O(M+N),空间复杂度O(M)*/
class Solution{
public:
	//KMP主程序,用预处理过的next数组来控制每次不匹配的偏移量,如果莫一个字符不匹配,那么直接找到needle中某一个字符和haystack的下一个字符匹配,这样永远不会回头,总匹配次数最多为字符串长度.
	int strStr(const string& haystack,const string& needle){
		if(needle.size()==0)return 0;
		vector<int> next=compute_next(needle);
		int q=-1;
		for(int i=0;i<haystack.size();i++){
			while(q>-1&&haystack[i]!=needle[q+1])
				q=next[q];
			if(haystack[i]==needle[q+1])
				q++;
			if(q==(needle.size()-1))
				return i-q;
		}return -1;
	}
//用来计算next数组的算法.具体原理参照算法导论32章.
	static vector<int> compute_next(const string& s){
		vector<int> next(s.size(),-1);
		if(s.size()==0)return next;
		int q=-1;
		for(int i=1;i<s.size();i++){
			while(q>-1&&s[i]!=s[q+1])//不匹配时要返回的位置
				q=next[q];
			if(s[i]==s[q+1])//如果下个字符匹配,那么直接继承之前的已匹配区域.
				q++;
			next[i]=q;
		}
		return next;
	}
};
int main(){
	string s1="ababcd";
	string needle="abc";
	Solution s;
	cout<<s.strStr(s1,needle)<<endl;
}