传送门

题意是说给两个字符串|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;
        }
    }
}