## 【DP】String Distance – 20HDU多校D2T12

### 传送门

|q|\leq10^5次询问，每次给出n的一个区间[l,r]

f[i][j]表示B[i]为止的，长度为jLCSA串的最短前缀长度。

f[i][j]=min(f[i-1][j],g[l+f[i-1][j-1]][b[i]]-l+1)

#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;
}
}
}