BJOI2015 隐身术

隐身术"/>

BJOI2015 隐身术

落谷。

Description

给你两个串 \(A、B\)。询问 \(B\) 中有多少个非空子串和 \(A\) 的编辑距离不超过 \(K\)。

Solution

发现 \(K \le 5\)，考虑可以爆搜。

考虑每个子串都是一个后缀的前缀，不妨枚举后缀，然后考虑对于这个后缀而言，能选几个符合条件的前缀作为子串。

对于每个后缀(起始下标为 \(L\))，设 \(\text{dfs(i, j, k)}\) 为当前需要匹配 \(A_i\) 和 \(B_j\)，还剩 \(k\) 次编辑的机会。

• 若 \(A_i = B_j\)，直接跳到下一个 \(A_{i + l} \not = B_{i + l}\) 最小的 \(l\) 的位置(因为已经相同不需要编辑)。

• 现在 \(A_i \not= B_j\) 了，说明必须要进行操作匹配上 \(A_i\)，还得保证 \(k > 0\)。

• 考虑插入一个字符匹配 \(A_i\) ：\(\text{dfs(x + 1, y, k - 1)}\) ；

• 考虑删除 \(B_j\) 字符 \(\text{dfs(x, y + 1, k - 2)}\)；

• 考虑替换 \(B_j\) 字符变成和 \(A_i\) 字符相同的 \(\text{dfs(x + 1, y + 1, k - 1)}\)。

• 如果 \(i > |A|\) 或 \(j > |B|\)(如果后者成立前者不成立说明少字符，还需 $k = k - (|A| - i + 1) $)，如果 \(k \ge 0\)，说明这次搜索成功了。特别地，考虑 \(k > 0\) 的情况，考虑还能用 \(k\) 次，所以可以少 $ \le k$ 个字符，然后人为加上，也可以再多加 \(\le k\) 个字符，然后用 \(k\) 个编辑机会减掉。设 \(vis[i]\) 为长度为 \(i\) 的前缀是否符合条件，所以这种 \(\text{dfs}\) 出的方案贡献的前缀区间是 \([\max(1, j - k - L), min(|B|, j + k - L)]\) 的 \(vis\) 数组全体赋值为 \(\text{True}\)。注意不同的 \(\text{dfs}\) 可能让同一个前缀都可以作为匹配，所以要去重，这种东西记录一个 \(\text{vis}\) 数组就行了。用差分可以把最后的循环优化掉，考虑答案区间分布在 \([|A| - k, |A| + k]\) (目标串与你的子串长度最大差异为 \(K\))。

考虑 \(K \le 5\)，所以每次 \(\text{dfs}\) 复杂度 \(O(3^5)\) 的。

对于第一个情况，需要知道他们的最长公共前缀 \(\text{lcp}\)，这个玩意可以后缀数组 + ST 表 \(O(1)\) 求，也可以二分 + Hash \(O(\log N)\) 求，但是这题好像时限挺紧的 后缀数组 都 \(2e7\) 了。

时间复杂度

\(O(3^5N)\)

Code

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;const int N = 100005;typedef long long LL;int K;int n, m = 127, t, p, len1, len2, height[N], oldrk[N << 1], rk[N], cnt[N], id[N];
int sa[N], st[N][17], Log[N], ans = 0;char s[N];bool inline cmp(int i, int j, int k) {return oldrk[i] == oldrk[j] && oldrk[i + k] == oldrk[j + k];
}inline void SA() {for (int i = 1; i <= n; i++) cnt[rk[i] = s[i]]++;for (int i = 2; i <= m; i++) cnt[i] += cnt[i - 1];for (int i = n; i; i--) sa[cnt[rk[i]]--] = i;for (int w = 1; w < n; w <<= 1, m = p) {p = 0;for (int i = n; i > n - w; i--) id[++p] = i;for (int i = 1; i <= n; i++)if (sa[i] > w) id[++p] = sa[i] - w;for (int i = 1; i <= m; i++) cnt[i] = 0;for (int i = 1; i <= n; i++) cnt[rk[i]]++;for (int i = 2; i <= m; i++) cnt[i] += cnt[i - 1];for (int i = n; i; i--)sa[cnt[rk[id[i]]]--] = id[i], oldrk[i] = rk[i];p = 0;for (int i = 1; i <= n; i++)rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;}for (int i = 1; i <= n; i++) {int j = sa[rk[i] - 1], k = max(0, height[rk[i - 1]] - 1);while (s[i + k] == s[j + k]) k++;height[rk[i]] = k;}for (int i = 1; i <= n; i++) Log[i] = log2(i), st[i][0] = height[i];for (int j = 1; j <= Log[n]; j++) {for (int i = 1; i + (1 << j) - 1 <= n; i++)st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);}
}int inline lcp(int l, int r) {if (l > r) swap(l, r);++l;int k = Log[r - l + 1];return min(st[l][k], st[r - (1 << k) + 1][k]);
}void dfs(int i, int j, int k) {int l = lcp(rk[i], rk[j + len1 + 1]);i += l, j += l;if (i > len1 || j > len2) {int d = k - (len1 - i + 1);if (d < 0) return;int l = max(1, j - d - t), r = min(len2 - t + 1, j + d - t);cnt[l]++; cnt[r + 1]--;return;} else if (k) {dfs(i + 1, j, k - 1);dfs(i, j + 1, k - 1);dfs(i + 1, j + 1, k - 1);}
}int main() {scanf("%d%s", &K, s + 1);len1 = strlen(s + 1);s[len1 + 1] = '#';scanf("%s", s + len1 + 2);n = strlen(s + 1);len2 = n - len1 - 1;SA();for (int i = 1; i <= m; i++) cnt[i] = 0;int L = max(1, len1 - K), R = min(len2, len1 + K);for (int i = 1; i <= len2; i++) {t = i;dfs(1, i, K);for (int j = L; j <= R; j++) cnt[j] += cnt[j - 1];for (int j = L; j <= R; j++) if (cnt[j]) cnt[j] = 0, ans++;}printf("%d\n", ans);
}