算法之KMP算法
KMP算法
概念:
- KMP算法是用于解决字符串匹配的问题的算法,也就是有一个文本串和一个模式串,求解这个模式串是否在文本串中出现或者匹配。
- 相对于暴力求解,KMP算法使用了前缀表来进行匹配,充分利用了之前匹配的字符,减少了重新匹配全部模式串的时间。
- 时间复杂度为O(m+n),其中n为文本串长度,m为模式串长度。
前缀表:
例子:文本串:‘aabaabaaf’ ,模式串:‘aabaaf’
前缀表也就是记录模式串的各子串最长相等前后缀长度(即字符串的前缀和后缀相等并且长度最长)的数组,而在KMP算法中是对模式串求解前缀表
前缀:字符串除了尾字符的子字符串都是前缀,模式串的前缀有:a、aa、aab、aaba、aabaa
后缀: 字符串除了首字符的子字符串都是后缀,模式串的后缀有:f、af、aaf、baaf、abaaf
根据上述的例子可以列出表格:
这样就对应着:aabaaf 010120,这个就为前缀表,而前缀表在KMP算法中被称为
next数组
或者prefix数组
。next的意思就是指通过这个数组可以知晓下一步指针会跳到哪一步。
求解next数组:
注:在遍历模式串的各个子串时,i为当前子串的后缀末尾索引,j为当前字串的前缀末尾索引并且为数组索引小于等于i之前的子串的最长相等前后缀长度。子串是连续的字符形成的
初始化
:j初始化为0,因为模式串的第一个前缀子串为第一个字符,所以j索引指向0的位置,并且next[0]=0,i初始化为1,用一个循环从索引i开始遍历模式串。(因为只有一个字符的子串没有相等前后缀)前后缀不相同情况
:为了充分利用之前已经匹配的字符,我们将对发生冲突的地方也就是前后缀末尾字符不匹配的时候,我们将对前缀末尾索引进行回溯到索引为next[j-1]的位置。前后缀相同情况
:当前后缀末尾字符相等的时候,就可以将j++,不仅将当前子串更新到下一个子串,还更新了当前子串的最长相等前后缀长度也就是next[i]=j
实现代码:
void getnext(int *next,const string& s,int size){
//初始化
int j=0;
next[0]=0;
for(int i=1;i<size;i++){
//前后缀不相等情况
while (j>0&&s[i]!=s[j]){
j=next[j-1]; //回溯找到相等位置或者回到0
}
//前后缀相同情况
if(s[i]==s[j]) j++;
next[i]=j;
}
}
KMP具体操作:
求解next数组
- 然后利用求解next数组同等思路,
求解文本串出现模式串位置的索引
,求解next数组是模式串前后缀末尾字符的比较,而文本串模式串匹配过程,是文本串与模式串的字符比较过程。 - 当j也就是文本串在索引大于等于i之前的子串与模式串最长匹配字符长度等于模式串的长度,就说明文本串出现了模式串,然后返回文本串中出现模式串的第一个字符的索引值
(i-j+1)
。
KMP算法总体实现代码:
void getnext(int *next,const string& s,int size){
//初始化
int j=0;
next[0]=0;
for(int i=1;i<size;i++){
//前后缀不相等情况
while (j>0&&s[i]!=s[j]){
j=next[j-1]; //回溯找到相等位置或者回到0
}
//前后缀相同情况
if(s[i]==s[j]) j++;
next[i]=j;
}
}
int KMP(const string &text,const string &mode){
int len=text.size();
if(len==0) return 0;
int size=mode.size();
int j=0,next[size];
getnext(next,mode,size);
for(int i=0;i<len;i++){
while (j>0&&text[i]!=mode[j]){
j=next[j-1];
}
if(text[i]==mode[j]) j++;
if(j==size) return (i-j+1);
}
return -1; //未找到模式串
}