【DP】String Distance – 20HDU多校D2T12
传送门
题意是说给两个字符串|n|\leq10^5,|m|\leq20。
有|q|\leq10^5次询问,每次给出n的一个区间[l,r]。
求区间内与字符串M的编辑距离(只有插入和删除操作)。
做法是先发现插入操作是无用的,因为再某个点插入可以等价转化为把对面字符串的对应位置删掉。所以ans=[l,r]+|m|-2LCS
那如何快速求最长公共子序列,要先发现m其实很小只有20。所以可以用另外一种求LCS的方法:
f[i][j]表示B[i]为止的,长度为j的LCS的A串的最短前缀长度。
同时用另外一个g[i][j]表示A[i] \to A[n]内字符j第一次出现的位置。
f[i][j]=min(f[i-1][j],g[l+f[i-1][j-1]][b[i]]-l+1)
这样求一次LCS复杂度为O(m^2)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int e[maxn][30], f[22][22];
char s[maxn], p[30];
int main()
{
freopen("1012.in", "r", stdin);
freopen("r.txt", "w", stdout);
cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
int T; cin >> T;
while(T--)
{
cin >> (s + 1) >> (p + 1);
int n = strlen(s + 1), m = strlen(p + 1);
for(int i = 'a'; i <= 'z'; i++) e[n + 1][i - 'a'] = n + 1;
for(int i = n; i > 0; i--)
{
for(int j = 'a'; j <= 'z'; j++)
e[i][j - 'a'] = e[i + 1][j - 'a'];
e[i][s[i] - 'a'] = i;
}
// cerr << e[2]['q' - 'a'] << endl;
int q; cin >> q;
while(q--)
{
int l, r; cin >> l >> r;
memset(f, 0x3f, sizeof f);
for(int i = 0; i <= m; i++) f[i][0] = 0;
int len = r - l + 1, ans = 0;
for(int j = 1; j <= m; j++)
{
for(int i = 1; i <= m; i++)
{
f[i][j] = min(f[i - 1][j], f[i][j]);
int prelen = f[i - 1][j - 1];
if(l + prelen <= r && e[l + prelen][p[i] - 'a'] <= r)
f[i][j] = min(f[i][j], e[l + prelen][p[i] - 'a'] - l + 1);
if(f[i][j] <= len) ans = max(ans, j);
}
}
// cerr << f[3][3] << endl;
cout << len + m - 2 * ans << endl;
}
}
}
发表评论