KMP模板
作者:
风城玫瑰.01
,
2023-11-30 20:16:28
,
所有人可见
,
阅读 86
利用KMP求子串在父串中出现的位置
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e4 + 10 , M = 1e5 + 10;
int n,m;
char s[N],p[M];//s[]为子串,p[]为父串
int ne[N];
int main()
{
cin >> n >> m;
cin >> s + 1 >> p + 1;
for( int i = 2 , j = 0 ; i <= n ; i ++ )
{
while(j > 0 && s[i] != s[j + 1]) j = ne[j];
if(s[i] == s[j + 1]) j ++ ;
ne[i] = j;
}
for( int i = 1 , j = 0 ; i <= m ; i ++ )
{
while(j > 0 && p[i] != s[j + 1]) j = ne[j];
if(p[i] == s[j + 1]) j ++ ;
if(j == n)
{
cout << i - n;
//j = ne[j];如存在多个子串+此Code
}
}
return 0;
}