杭电第二场1012 String Distance 序列自动机+DP

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6774
题目大意：

对于操作：删除一个字符或者添加一个字符
给你两个字符串A，B。q次询问，每次询问A串的A[l...r]最少通过多少次操作变成B。

思路：通过序列自动机得到一个数组：net[i][j]:A[i-]后面第一个j字符的位置。
然后每次一个DP：f[i][j]:B前i个字符匹配了j个字符的子序列的最近位置。
转移：

我们推导出：最少操作次数=r-l+m-*LCS

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

char a[2000005], b[105];
int nxt[2000005][26];
int n, m;

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

        int q;
        scanf("%d", &q);
        while(q--) {
            int l, r;
            scanf("%d%d", &l, &r);
            int mx=0;

            int f[25][25];
            memset(f, 0x3f, sizeof(f));
            f[0][0]=l-1;
            for(int i=1; i<=m; i++){
                for(int j=0; j<=i; j++){
                    f[i][j]=f[i-1][j];
                    if(j>=1&&f[i-1][j-1]!=f[23][23]){
                        f[i][j]=min(f[i][j], (nxt[f[i-1][j-1]][b[i]-'a']==0)?f[23][23]:nxt[f[i-1][j-1]][b[i]-'a']);
                    }
                    if(f[i][j]<=r){
                        mx=j;
                    }
                }
            }

            printf("%d\n",r-l+1-2*mx+m);
        }

    }
}