KMP算法

2024-08-11

通过求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;
}