首页 > 代码库 > kmp
kmp
#include <bits/stdc++.h>
#define MAXN 100000
using namespace std;
string a, b;
int next[MAXN]; //****a为主串,b为模式串
void get_next(void) //***获得next数组
{
next[0] = 0;
for(int i=1, j=0; i<b.size(); i++)
{
while(j>0 && b[i]!=b[j])
{
j=next[j-1]; //***求next数组即模式串自身匹配的过程,失配时通过将j后移使其能继续匹配
}
if(a[i]==b[j]) //***当前字符匹配成功则继续向后匹配
{
j++;
}
}
}
int kmp(void)
{
get_next();
for(int i=0, j=0; i<a.size(); i++)
{
while(j>0 && a[i]!=b[j])
{
j=next[j-1]; //****失配时通过将j后移使之能继续往后匹配
}
if(a[i]==b[j]) //****当前字符匹配成功则继续往后匹配
{
j++;
}
if(j==b.size())
{
return i-j+1; //****如果匹配成功,返回首字符的下标;
}
}
return 0;
}
int main(void)
{
cin >> a >> b;
int ans=kmp();
if(ans)
{
cout << "YES" << endl << ans << endl;
}
else
{
cout << "NO" << endl;
}
fflush(stdout);
return 0;
}
kmp