通过求Next数组,确定失配后指针移动到的位置,从而实现快速字符串匹配
#include <bits/stdc++.h>
#define io cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define LL long long
#define ULL unsigned long long
#define EPS 1e-7
#define INF 0x7fffffff
#define SUB -INF - 1
using namespace std;
const int N = 1005;
char str[N], pattern[N];
int Next[N];
void getNext(char *p, int plen)
{
Next[0] = 0, Next[1] = 0;
for (int i = 1; i < plen; i++)
{
int j = Next[i];
while (j && p[i] != p[j])
j = Next[j];
if (p[i] == p[j])
Next[i + 1] = j + 1;
else
Next[i + 1] = 0;
}
}
int kmp(char *s, char *p)
{
int slen = strlen(s), plen = strlen(p);
getNext(p, plen);
int j = 0;
for (int i = 0; i < slen; i++)
{
while (j && s[i] != p[j])
j = Next[j];
if (s[i] == p[j])
j++;
if (j == plen)
return i + 1 - plen;
}
return -1;
}
int main()
{
cin >> str >> pattern;
cout << kmp(str, pattern);
return 0;
}