773 字
4 分钟
KMP算法
KMP(Knuth-Morris-Pratt)算法是一种高效的字符串匹配算法。其核心精髓在于:当匹配失败时,能够利用已匹配的信息,避免模式串指针的回溯,实现“原地”跳跃。
1. 核心逻辑:next 数组(前缀函数)
next[i] 的定义是:模式串 P 从第 1 位到第 i 位组成的字符串中,最长公共前后缀的长度。
代码实现
// 模式串 P 从 1 开始,长度为 nne[1] = 0;for (int i = 2, j = 0; i <= n; i++) { // 如果当前字符不匹配,j 持续回退到 ne[j] while (j && P[i] != P[j + 1]) j = ne[j]; // 如果匹配,最长公共前后缀长度 j 加 1 if (P[i] == P[j + 1]) j++; // 记录结果 ne[i] = j;}- 为何会有
j = ne[j]? 当P[i] != P[j+1]时,说明以i结尾的匹配串出现了失配,我们需要找一个比当前j更短的、已经处理过的后缀能与之重合的部分前缀。
2. 复杂度证明
这里KMP计算next数组的复杂度直观上很难分析,我们可以考虑j的贡献来分析整体的复杂度。 我们可以考虑j的总增加次数和减少次数:
- 增加次数:在整个
for循环中,i从 2 到 。j只有在P[i] == P[j + 1]时才会执行j++,这意味着j在整个生命周期中最多增加 次。 - 减少次数:
while循环中的j = ne[j]操作会使j减小。因为j的值始终大于等于 0,j减少的总次数不可能超过它增加的总次数。 因此,总的操作开销 = 。
例题 P16231 [蓝桥杯 2026 省 A] 基因研究 dp[i][j]的意义是第i位匹配到易感基因第j位的概率,匹配失败时需要用next数组,提前预处理出来在dp时使用
#include <bits/stdc++.h>#include <cstdlib>#define ll long long#define N 100005#define pr pair<ll, ll>using namespace std;int n, m, cnt, vv;const ll mod = 998244353;int main() { ios::sync_with_stdio(0); cin >> n >> m; string s; map<char, int> mp; mp['A'] = 0; mp['T'] = 1; mp['G'] = 2; mp['C'] = 3; cin >> s; vector<int> gene; gene.push_back(0); for (auto x : s) { gene.push_back(mp[x]); } vector<int> next(m + 5, 0); next[1] = 0; for (int i = 2, j = 0; i <= m; i++) { while (j && gene[i] != gene[j + 1]) j = next[j]; if (gene[i] == gene[j + 1]) j++; next[i] = j; } vector<vector<int>> to(m + 5, vector<int>(5, 0)); for (int j = 0; j < m; j++) { for (int ch = 0; ch < 4; ch++) { int now = j; while (now && gene[now + 1] != ch) now = next[now]; if (gene[now + 1] == ch) now++; to[j][ch] = now; } } vector<ll> p(5, 0); vector<vector<ll>> dp(n + 5, vector<ll>(m + 5, 0)); dp[0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j < 4; j++) { cin >> p[j]; } for (int j = 0; j <= min(i - 1, m - 1); j++) { for (int ch = 0; ch < 4; ch++) { dp[i][to[j][ch]] = (dp[i][to[j][ch]] + dp[i - 1][j] * p[ch]) % mod; } } } ll res = 0; for (int j = 0; j < m; j++) res = (res + dp[n][j]) % mod; cout << (1 - res + mod) % mod; return 0;}分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 74 天
部分内容可能已过时