浅谈KMP算法
2020-04-11 本文已影响0人
劭星
文章转自我的csdn博客
被遮住代码块：
1.
bool check(int pos)
{
for(int i=pos,j=0;j<m;i++,j++)
if(text[i]!=pattern[j])
return false;
return true;
}
void solve()
{
//n表示text长度，m表示pattern长度
int ans=-1;
for(int i=0;i<n;i++)
if(check(i))
ans=i,break;
cout<<ans<<endl;
}
2.
void get_next()
{
next[0]=-1;//在0这个位置不存在任何最大前后缀（情况三）
int k=-1;
for(unsigned int i=1;i<pattern.size();i++)
{
while(k>-1 && pattern[k+1] != pattern[i])//情况二
k=next[k];
if(pattern[k+1]==pattern[i])//情况一
k++;
next[i]=k;
}
}
3.
void kmp()
{
int k=-1;
for(unsigned int i=0;i<text.size();i++)
{
while(k>-1 && pattern[k+1]!=text[i])
k=ne[k];
if(pattern[k+1]==text[i])
k++;
if(k==pattern.size()-1)
{
return i-k;
}
}
return -1;
}
