时间戳

首页 > 技术文章 > 正睿1595 「20联赛集训day1」打字机（区间编辑距离查询问题）

正睿1595 「20联赛集训day1」打字机（区间编辑距离查询问题）

dysyn1314 2020-11-21 10:25 原文

正睿1595 [20联赛集训day1]打字机（区间编辑距离查询问题）

题目大意

给定两个串 \(S\), \(T\)。\(q\) 次询问，每次查询 \(S\) 的一个子串 \(S[l,r]\) 和 \(T\) 的编辑距离。

两串 \(A,B\) 的编辑距离定义为，通过进行插入、删除、替换的操作（每次操作选择其中一种），将 \(A\) 变成 \(B\) 所需的最小操作次数。

数据范围：\(1\leq |S|,q\leq 10^5\)，\(1\leq |T|\leq 20\)。

本题题解

朴素 DP

抛开多次询问。只考虑对两个串 \(A\), \(B\)，求他们的编辑距离。

可以做一个朴素 DP。设 \(\text{dp}_0(i,j)\) 表示 \(A[1,i]\) 和 \(B[1,j]\) 的编辑距离（\(\text{dp}_0\) 是为了和后面的其他 DP 区分开来）。则转移有三种：

\[\begin{cases} \text{dp}_0(i,j) + 1 &\to\text{dp}_0(i + 1,j)\\ \text{dp}_0(i,j) + 1 &\to\text{dp}_0(i,j + 1)\\ \text{dp}_0(i,j) + [A_{i + 1}\neq B_{j + 1}] &\to \text{dp}_0(i + 1, j + 1) \end{cases} \]

一次 DP 的复杂度是 \(O(|A||B|)\)。

在本题里，总复杂度是 \(O(q|S||T|)\)。

正解

先讨论一个一般性的问题。对于一个串 \(A\)，考虑它所有后缀与另一个串 \(B\) 的编辑距离。设 \(A\) 的长度为 \(x\) 的后缀与 \(B\) 的编辑距离为 \(h(x)\)。我们发现，函数 \(F(x) = x-h(x)\) 有很好的性质。

  • 首先，\(F(x) = x - h(x)\) 单调不降。这很好证明，因为当 \(x\) 加 \(1\) 时（后缀的长度加 \(1\)，即在开头增加一个字符），\(h(x)\) 最多加 \(1\)（最坏情况就是直接把新加的字符删掉，用 \(1\) 次操作）。
  • 其次，\(F(x) = x - h(x)\) 的值域是很有限的。因为 \(h(x)\leq x + |B|\)，且 \(h(x)\geq x-|B|\)，所以 \(-|B|\leq F(x)\leq |B|\)。

回到本题。\(S\) 的每个子串都可以表述为 \(S\) 的一个前缀的后缀。所以为了回答询问，我们要对 \(S\) 的每个前缀，预处理出关于它所有后缀的信息。即，我们要对所有：\(A\) 是 \(S\) 的一个前缀，\(B\) 是 \(T\)，的情况，维护出 \(F_{A,B}(x)\)。

那么朴素的做法是，设 \(\text{dp}_1(i,j,x)\) 表示 \(F_{S[1,i],T[1,j]}(x)\)。仿照上述的朴素 DP，可以 \(O(1)\) 转移。最后对于询问 \(l,r\)，答案就是：\(r - l + 1 -\text{dp}_1(r,|T|,r - l + 1)\)。时间复杂度 \(O(|S|^2|T|+q)\)。

继续优化，前面说过，\(F(x)\) 有一个很好的性质，就是值域很小。所以考虑将 DP 的下标与值域互换。重新定义状态：设 \(\text{dp}_2(i,j,k)\) 表示使得 \(F_{S[1,i],S[1,j]}(x)\leq k\) 的最大的 \(x\)。

转移还是仿照朴素 DP 中的三种情况：

\[\begin{cases} \text{dp}_2(i,j,k) + 1 & \to \text{dp}_2(i + 1,j,k)\\ \text{dp}_2(i,j,k)&\to \text{dp}_2(i,j + 1, k - 1)\\ \text{dp}_2(i,j,k) + 1 &\to \text{dp}_2(i + 1, j + 1, k + [S_{i + 1}=T_{j + 1}]) \end{cases} \]

你可以直接按照编辑距离来理解（和朴素 DP 是类似的）。也可以按照分段函数的合并来理解。在朴素合并分段函数时（也就是 \(\text{dp}_1\)），函数值是对能转移到它的三种值取 \(\max\)。那新的 DP 中，对于同一个函数值，我们希望它出现的位置越早越好，所以 \(\text{dp}_2\) 的转移应该是取 \(\min\)。

DP 的边界也比较重要。考虑 \(F_{A,B}(x)\) 函数，\(x\) 的定义域应该是 \([0,|A|]\)。但是为了方便 DP，我们定义 \(F(-1)=-\infty\)。这样 DP 的边界就是：\(\forall i,j:\forall k \in[-m-1,-j):\text{dp}_2(i,j,k)=-1\)。\(\text{dp}_2(0,0,0)=0\)。其他 \(\text{dp}_2(i,j,k) = \infty\)。

DP 的时间复杂度 \(O(|S||T|^2)\)。空间复杂度，用滚动数组优化后，可以做到 \(O(|T|^2)\)。

对于询问 \(l,r\)。我们从小到大枚举 \(k\)，找到第一个使得 \(\text{dp}_2(r,|T|,k)\geq r - l + 1\) 的 \(k\)，则答案就是 \(r-l+1-k\)。单次查询的时间复杂度 \(O(|T|)\)。显然可以通过二分查找优化到 \(O(\log |T|)\)，不过意义不大。

总时间复杂度 \(O(|S||T|^2+q|T|)\)。

参考代码

本题可能需要使用读入、输出优化，详见本博客公告。

// problem: ZR1595
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }

const int MAXN = 1e5, MAXM = 20;
const int INF = 1e9;
int n, m, q;
char s[MAXN + 5], t[MAXM + 5];

int dp[2][MAXM + 5][MAXM * 2 + 5];
int g[MAXN + 5][MAXM * 2 + 5];
int main() {
	cin >> (s + 1) >> (t + 1) >> q;
	n = strlen(s + 1);
	m = strlen(t + 1);
	int B = m + 1;
	for (int j = 0; j <= m; ++j) {
		for (int k = -j; k <= m; ++k) {
			dp[0][j][k + B] = INF;
		}
		for (int k = -m - 1; k < -j; ++k) {
			dp[0][j][k + B] = -1;
		}
	}
	dp[0][0][B] = 0;
	for (int i = 0; i <= n; ++i) {
		int cur = (i & 1);
		int nxt = (cur ^ 1);
		for (int j = 0; j <= m; ++j) {
			for (int k = -j; k <= m; ++k) {
				dp[nxt][j][k + B] = INF;
			}
			for (int k = -m - 1; k < -j; ++k) {
				dp[nxt][j][k + B] = -1;
			}
		}
		for (int j = 0; j <= m; ++j) {
			for (int k = -m - 1; k <= m; ++k) {
				// cerr << "** " << i << " " << j << " " << k << " " << dp[i][j][k + m] << endl;
				if (i < n)
					ckmin(dp[nxt][j][k + B], dp[cur][j][k + B] + 1);
				if (j < m)
					ckmin(dp[cur][j + 1][k - 1 + B], dp[cur][j][k + B]);
				if (i < n && j < m)
					ckmin(dp[nxt][j + 1][k + (s[i + 1] == t[j + 1]) + B], dp[cur][j][k + B] + 1);
			}
		}
		for (int k = -m; k <= m; ++k) {
			g[i][k + B] = dp[cur][m][k + B];
		}
	}
	for (int tq = 1; tq <= q; ++ tq) {
		int l, r;
		cin >> l >> r;
		int len = r - l + 1;
		for (int k = -m; k <= m; ++k) {
			if (g[r][k + B] >= len) {
				cout << len - k << endl;
				break;
			}
		}
	}
	return 0;
}

推荐阅读