最少得分子序列
给你两个字符串 s 和 t 。
你可以从字符串 t 中删除任意数目的字符。
如果没有从字符串 t 中删除字符，那么得分为 0 ，否则：
令 left 为删除字符中的最小下标。
令 right 为删除字符中的最大下标。
字符串的得分为 right - left + 1 。
请你返回使 t 成为 s 子序列的最小得分。
一个字符串的 子序列 是从原字符串中删除一些字符后（也可以一个也不删除），剩余字符不改变顺序得到的字符串。（比方说 "ace" 是 "abcde" 的子序列，但是 "aec" 不是）。
示例 1：
输入：s = "abacaba", t = "bzaa"
输出：1
解释：这个例子中，我们删除下标 1 处的字符 "z" （下标从 0 开始）。
字符串 t 变为 "baa" ，它是字符串 "abacaba" 的子序列，得分为 1 - 1 + 1 = 1 。
1 是能得到的最小得分。
示例 2：
输入：s = "cde", t = "xyz"
输出：3
解释：这个例子中，我们将下标为 0， 1 和 2 处的字符 "x" ，"y" 和 "z" 删除（下标从 0 开始）。
字符串变成 "" ，它是字符串 "cde" 的子序列，得分为 2 - 0 + 1 = 3 。
3 是能得到的最小得分。
提示：
1 <= s.length, t.length <= 105
s 和 t 都只包含小写英文字母。
思路：开始我们可以发现一个性质，就是一个序列t是另一个序列s的子序列，那么这就代表序列t的子序列均是序列s的子序列。因此按照题目要求，删除\(left\)到\(right\)中的任何数量字符得到的序列，均有一子序列是删除\(left\)到\(right\)中的所有数量字符得到的序列。那么好了，我们为了方便，就把他全删了，这样留下前缀\(X\)与后缀\(Y\),我们只需要\(check\)字符串\(X+Y\)是否满足条件就ok。
如何\(check\)前后缀是否满足呢？利用子序列自动机就可以，子序列自动机可以看作在字符串s上每一个字符均有\(26\)个指针，\(f[i,j]\)表示字符串第\(i\)个位置的下一个字符为\('a'+j\)的下标。维护子序列自动机，实现看代码。然后利用二分来\(check\)因为具有同样的子序列关系。具体看代码（也可以用双指针，我认为二分答案好写，就用的二分）
\(Code\)
class Solution {
public:
int a[100100][26],b[100100][26],pre[33],bep[33];
void work(string s){
int len = s.size() - 1;
for(int i=0;i<=25;++i)pre[i] = len+1;
for (int i = len; i >= 0; --i) {
int id = s[i] - 'a';
for(int j=0;j<=25;++j){
a[i][j] = pre[j];
}
if(i == 0)break;
pre[id] = i;
}
for (int i = 1; i <= len+1; ++i) {
int id = s[i] - 'a';
for (int j = 0; j <= 25; ++j) {
b[i][j] = bep[j];
}
if(i == len+1)break;
bep[id] = i;
}
}
int lens,lent ;
string ss,tt ;
int arr[100010],brr[100010];
bool check(int k){
if(k == lent)return true;
if(brr[k+1]!=0 and brr[k+1]!=lens+1)return true;
if(arr[lent-k]!=0 and arr[lent-k]!=lens+1)return true;
for(int i=1;;++i){
int x = i,y = i+k+1;
if(y>lent)break;
if(brr[y]==0||brr[y]==lens+1)continue;
if(arr[x]==0||arr[x]==lens+1)return false;
int idx = arr[x],idy = brr[y];
if(idx < idy){
return true;
}
}
return false;
}
int minimumScore(string s, string t) {
s = "1" + s;
t = "1" + t;ss = s;tt = t;
work(s);
lens = s.size() - 1;
lent = t.size() - 1;
int idx = 0;
for(int i=1;i<=lent;++i){
int num = t[i] - 'a';
idx = a[idx][num];
arr[i] = idx;
if(idx == 0||idx == lens+1)break;
}
idx = lens+1;
for(int i=lent;i>=1;--i){
int num = t[i] - 'a';
idx = b[idx][num];
brr[i] = idx;
if(idx == 0||idx == lens+1)break;
}
int l = 0,r = lent;
while(l < r){
int mid = l + r >> 1;
if(check(mid)){
r = mid;
}else l = mid + 1;
}
return l;
}
};