2020HDU多校第二场 String Distance

题意：给定A,B字符串，询问A字符串的[l,r]子字符串最少多少次操作能够变成B字符串。(可以操作A串，也可以操作B串)
操作： 增加一个字符，或者减少一个字符。

分析:因为只能插删，所以最优的肯定是留下最长公共子序列。
表示到 串的第 个位置，长度为 的子序列，在 串的最小位置。
序列自动机预处理一下 串，然后每次询问做一遍 的dp.

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=2e5+10;

char a[maxn],b[maxn];
int nex[maxn][26],t,f[22][22];

int main()
{
    scanf("%d",&t);
    while( t-- )
    {
        scanf("%s%s",a+1,b+1);
        int n=strlen(a+1);
        int m=strlen(b+1);
        for( int i=0;i<26;i++ ) nex[n+1][i]=0;
        for( int i=n;i>=1;i-- )
        {
            for( int j=0;j<26;j++ ) nex[i][j]=nex[i+1][j];
            nex[i][a[i]-'a']=i;
        }

        int q;
        scanf("%d",&q);
        while( q-- ) 
        {
            int l,r;
            scanf("%d%d",&l,&r);
            for( int i=0;i<=m;i++ )
            for( int j=0;j<=m;j++ ) f[i][j]=-1;
             // 前i个字符 匹配了j位子序列 的最短 a串位置
            for( int i=0;i<=m;i++ ) f[i][0]=l-1;
            int y=0;

            for( int i=1;i<=m;i++ )
            {
                for( int j=i-1;j>=0;j-- )
                {
                    int x=f[i-1][j];
                    f[i][j+1]=f[i-1][j+1];
                    if( x==-1 ) continue;
                    if( nex[x+1][b[i]-'a'] && nex[x+1][b[i]-'a']<=r )
                    {
                        if( f[i][j+1]==-1 ) f[i][j+1]=nex[x+1][b[i]-'a'];
                        else f[i][j+1]=min(f[i][j+1],nex[x+1][b[i]-'a']);
                        y=max(y,j+1);
                    }
                }
            }
            printf("%d\n",r-l+1+m-2*y);
        }
    }
}