KMP算法
KMP算法
KMP算法 是一个解决模式串在文本串是否出现过,如果出现过,最早出现的位置的经典算法。
重点是找到字符串的最长公共前后缀。用最长公共前后缀在匹配的同时,实现快速跳转。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int Maxn = 1e6 + 5;
int la, lb;
int nxt[Maxn];
char a[Maxn], b[Maxn];
inline void kmp() { //字符串: 1 ~ lb;
nxt[1] = 0;
for (int i = 2, j = 0; i <= lb; i++) { // 求 nxt[1~lb]; nxt[i]为(包括第i位)最长公共前后缀;
while (j && b[i] != b[j + 1]) j = nxt[j]; // 子问题思想,让模式串(b串)后移找到前缀,即 j=nxt[j];
if (b[i] == b[j + 1]) j++; // 如果是因为 j==0 退出的 while循环,不执行 j++;
nxt[i] = j;
}
for (int i = 1, j = 0; i <= la; i++) { // i是主串的指针,j是模式串的指针;
while (j && a[i] != b[j + 1]) j = nxt[j]; // 匹配失败;
if (a[i] == b[j + 1]) j++; // 匹配成功;
if (j == lb) {
printf("%d\n", i - lb + 1); // 找到出现的位置,实际上为 i-lb;
j = nxt[j];
}
}
}
int main() {
scanf("%s%s", a + 1, b + 1);
la = strlen(a + 1);
lb = strlen(b + 1);
kmp();
for (int i = 1; i <= lb; i++) printf("%d ", nxt[i]);
return 0;
}
热门相关:火力法则 女王嫁到:老公,太凶了 天命为妃 调教初唐 极品明君