当前位置：首页 > news >正文

算法·KMP

news 2025/7/3 9:34:07

KMP算法的思想

想要一次性遍历模板串 $s_1$ ，不在匹配失败时重新开始遍历子串 $s_2$ ，实现模板串不回退的效果。

KMP数组的理解

KMP数组有两种定义：一是匹配失败后，子串 $s_2$ 应该回退的位置，一种是 $s_2$ [0, i] 部分公共前后缀的长度。

模板+理解

第一个pos:子串的公共前后缀长度
第二个pos:使用KMP算法时，模板串和子串的公共长度

void solve() {cin >> a >> b;a = '0' + a;b = '0' + b;int lena = a.size() - 1, lenb = b.size() - 1,pos=0;//pos的含义:子串的公共前后缀长度kmp[1] = 0;for (int i = 2; i <= lenb; i++) {while (pos && b[pos + 1] != b[i])pos = kmp[pos];if (b[pos + 1] == b[i])pos++;kmp[i] = pos;}pos = 0;//pos的含义:模板串和子串的公共长度for (int i = 1; i <= lena; i++) {while (pos && a[i] != b[pos + 1])pos = kmp[pos];if (a[i]==b[pos+1])pos++;if (pos == lenb) {cout << i - lenb + 1<<endl;pos = kmp[pos];}}for (int i = 1; i <= lenb; i++) {cout << kmp[i] << " ";}
}

例题

P3375 【模板】KMP
P4391 [BalticOI 2009] Radio Transmission 无线传输:重复字符串，经典KMP题目。注意到原串蕴含重复的子串，左右两端有多出来的子串，但是找规律发现公共前后缀恰好可以表示多出来的子串。于是答案只需要减去多出来的子串就是重复子串的长度。

	for (int i = 2; i <= lena; i++) {while (pos!=0 && a[pos + 1] != a[i])pos = kmp[pos];if (a[pos + 1] == a[i])pos++;kmp[i] = pos;}cout << lena - kmp[lena];

P1470 [USACO2.3] 最长前缀 Longest Prefix：这题数据比较水，数据大概 $O(4*10^8)$ ,竟然不卡，用DP建模为背包问题。DP数组的定义是[0,i]是否可以被物体表示。物体就是P集合。

void solve() {int lenp = 0;while (1) {cin >> p;if (p != ".")P[++lenp] = p;else break;}while (cin >> tmp) {s += tmp;}s = '0' + s;//cout <<"s:"<< s << endl;int lens = s.size();dp[0] = true;for (int i = 1; i <= lens; i++) {for (int j = 1; j <= lenp;j++) {string item = P[j];if (i < item.size())continue;string subs = s.substr(i - item.size()+1, item.size());if (subs== item) {dp[i] = dp[i]||dp[i-item.size()];}}}int idx = 0;for (int i = 1; i <= lens; i++) {if (dp[i])idx = i;}cout << idx ;
}