登录
← 返回首页 | 代码片段 › 6 字符串 › 6.1 KMP › KMP / 搜索
JSON MD

6.1 KMP

KMP kmp
40 行
CPP JSON
【KMP(Knuth-Morris-Pratt)字符串匹配算法】 ▪ buildNext(pattern) — 构建 next 数组(前缀函数):对模式串每个位置 i,计算以 i 结尾的最长公共前后缀长度。失配时 j=next[j-1] 回退,O(M) ▪ search(text, pattern) — 在 text 中搜索 pattern:双指针扫描,匹配时 i++,j++;失配时若 j>0 则 j=next[j-1] 否则 i++,O(N+M) 无回溯匹配,效率远高于暴力。适用于单模式串匹配、字符串周期分析、最小循环节计算。
C++ 40 行 CPP
// KMP算法:构建next数组
vector<int> buildNext(const string& pattern) {
    int n = pattern.size();
    vector<int> next(n, 0);
    int j = 0;
    for (int i = 1; i < n; ++i) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

// KMP算法:在文本中查找模式串,返回所有匹配的起始位置
vector<int> kmpSearch(const string& text, const string& pattern) {
    vector<int> result;
    int n = text.size();
    int m = pattern.size();
    if (m == 0) return result;
    
    vector<int> next = buildNext(pattern);
    int j = 0;
    for (int i = 0; i < n; ++i) {
        while (j > 0 && text[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (text[i] == pattern[j]) {
            j++;
        }
        if (j == m) {
            result.push_back(i - m + 1);
            j = next[j - 1];
        }
    }
    return result;
}
KMP kmp
22 行
CPP JSON
【KMP】 KMP(Knuth-Morris-Pratt)字符串匹配模板,失配时利用前缀函数快速回退。 复杂度:预处理 O(M),匹配 O(N+M)
C++ 21 行 CPP
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int i,j,n,m,next[1000005];string a,b;
int main(){
	cin>>a>>b;
	n=a.size();a='$'+a;
	m=b.size();b='$'+b;
	for(i=2,j=0;i<=m;i++){
		while(j&&b[i]!=b[j+1])j=next[j];
		if(b[i]==b[j+1])j++;
		next[i]=j;
	}
	for(i=1,j=0;i<=n;i++){
		while(j&&a[i]!=b[j+1])j=next[j];
		if(a[i]==b[j+1])j++;
		if(j==m){j=next[j];printf("%d\n",i-m+1);}
	}
	for(i=1;i<=m;i++)printf("%d ",next[i]);
}
已复制