字符串查找问题:
给定文本串text和模式串pattern,要求从文本串中找到模式串第一次出现的位置。
解法:
暴力解法(Brute Force): 时间复杂度O(M*N),空间复杂度O(1).
kmp算法是对BF算法的改进,它是一种线性复杂度的算法,时间复杂度O(N),空间复杂度O(M)。
* 记文本串长度N,模式串M。
暴力求解:
对每个文本字符(假设位置为i)匹配,从模式串第一个位置开始向后匹配,相同往后,不同则从i+1重新匹配。
kmp:
我们先假设有这样一种情况:要匹配的模式串没有一个相同,那你能想到一种线性复杂度的算法吗?
假设目前A和B部分匹配上了,长度相同,i和j位置字符不同,按照暴力解法,我们要从k+1位置接着匹配。
但是现在有前提条件:假设匹配串全都不同 那是不是只要从i位置重新匹配就行了。
考虑这个很强的条件带给我们什么?
没错,就是匹配串的重复程度让我们知道从什么位置开始匹配更合理。
搞定了匹配程度,kmp算法就很jian简单了。
step1:
开一个数组next存储这种匹配程度,对于模式串的位置j,有next[j]=k,即
p[0]~p[k-1]==p[j-k]~p[j-1]. 则对位置j+1,考察p[j]
1.p[j]==p[k]
next[j+1]=next[j]+1.
2.p[j]!=p[k]
记h=next[k];如果p[h]==p[j],则next[j+1]==h+1,
重复此过程,若将h改为k,就是一个递归的过程。
最好自己画一下。
实现代码及其简单:
#include <bits/stdc++.h>
using namespace std;
const int maxn=10000000;
char p[maxn],s[maxn];
int next[maxn];
int pattern_len;
void getnext()
{
pattern_len=strlen(p);
next[0]=-1;
int k=-1,j=0;
while(j<pattern_len-1)
{
if(k==-1||p[j]==p[k])
{
++j; ++k;
next[j]=k;
}else{
k=next[k];
}
}
}
int kmp()
{
int ans=-1;
int i=0,j=0;
int n=strlen(s);
while(i<n)
{
if(j==-1||p[j]==s[i])
{
i++; j++;
}else j=next[j];
if(j==pattern_len)
{
ans=i-pattern_len+1;//字符以0开始,位置加一
break;
}
}
return ans;
}
int main()
{
while(1)
{
scanf("%s",s);//文本串
scanf("%s",p);//匹配串
getnext();
printf("%d\n",kmp());
}
return 0;
}