String Distance

题目链接

题目大意

给两个字符串a，b。
a的长度是1e5，b的长度是20.
有两种操作：
选一个串在随便哪个位置插入随便哪个字符。
随便删除一个字符。
有q次询问，每次询问给出一个l，r 问a串的 l ~ r 区间与b字符串，经过多少次操作，能使他们相等？
废话：
做的时候好菜，想到了跟lcs有关，感觉是最长的那个串减去lcs 再乘2。错的，啊啊啊啊啊好菜啊，也不会快速求这个lcs

题解

添加几个字符，不如删除。
所有的添加操作都可以被删除操作替代。
这个，，我没想到
然后 答案就是r - l + m - 2 * lcs长度 m代表b串长度。
这个很好想。
然后 怎么快速的找最长公共子序列？
题解告诉我，先预处理一下nex[i][j] 代表a串第i个位置以后j字符出现的第一个位置。。然后用dp求最长公共子序列的长度。复杂度是m*m
然后 总的复杂度就是n * 26 + m * m * q
怎么用dp求？
dp[i][j] 表示1~i中可以组成的最长公共子序列长度为j的最长长度。
转移方程就是

dp[i][j] = min(dp[i][j],nex[dp[i - 1][j - 1] + 1][b[i] - 'a']);

记得初始化！！！！！！！！！！！！！！
。。 真心想不出来，脑子是个好东西。。

代码

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#include <unordered_set>
#include <bitset>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef unsigned long long ull;
typedef set<int>::iterator sit;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void wenjian(){
   freopen("concatenation.in","r",stdin);freopen("concatenation.out","w",stdout);}
void tempwj(){
   freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){
   return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){
   a %= mod;ll ans = 1;while(b){
   if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp2{
   bool operator()(const pii & a, const pii & b){
   return a.second < b.second;}};
int lb(int x){
   return  x & -x;}
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

const int maxn = 2e5+5;


int nex[maxn][30]; // nex[i][j] 表示 i~n里 第一个字符j出现的位置的下标
int dp[30][30];
char a[maxn];
char b[31];
int main()
{
   
	int T;
	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 = 1; i <= n + 3; i ++ )
		{
   
			for (int j = 0; j < 26; j ++ )
			{
   
				nex[i][j] = n + 1;
			}
		}
		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;
		}
		// for (int i= 1; i <= n; i ++ )
		// {
   
		// for (int j = 0; j < 26; j ++ )
		// printf("%d ",nex[i][j]);
		// printf("\n");
		// }

		int q;
		scanf("%d",&q);
		while(q -- )
		{
   
			int l,r;
			scanf("%d%d",&l,&r);
			for (int j = 0; j <= m; j ++ )
			{
   
				for(int k = 0; k <= m; k ++ )
					dp[j][k] = inf;
			}
			dp[0][0]=  l - 1;
			int ans =0 ;
			for (int i = 1; i <= m; i ++ )
			{
   
				for (int j = i - 1; j >= 0; j -- )
				{
   
					dp[i][j] = dp[i - 1][j];
				}
				for (int j = i; j >= 1; j -- )
				{
   
					//printf("%d %d %d %d\n",i,j,b[i] - 'a',dp[i - 1][j - 1] );
					if(dp[i - 1][j - 1] == inf)
						continue;
					dp[i][j] = min(nex[dp[i - 1][j - 1] + 1][b[i] - 'a'],dp[i][j]);

					if(dp[i][j] <= r)
						ans = max(j,ans);
				}
			}
			// for (int i = 1; i <= m; i ++ )
			// {
   
			// for(int j = 1; j <= i; j ++ )
			// printf("%d ",dp[i][j]);
			// printf("\n");
			// }
			// cout<<ans<<endl;
			printf("%d\n",r - l + 1 + m - ans * 2);
		}
	}
}