题意

给你两个字符串 $a$ 和 $b$ ，你可以在 $b$ 中删去尽量短的子段，使得 $b$ 是 $a$ 的子序列。求出最后的 $b$ 。

思路

~~真是奇了怪了，这种题洛谷题解里竟然没有双指针的做法？~~

首先考虑判断一个字符串 $b$ 是否是另一个字符串 $a$ 的子序列。这个问题相信学过点 OI 的人都会做。

其实在做上面这个题的时候，因为贪心， $b$ 字符串的最右边字符对应在 $a$ 中一定是最靠左的。那么很容易，也可以求出 $b$ 的最左边字符在 $a$ 中最靠右的位置。

现在再看原题，其实就是把 $b$ 字符串分成前后两个部分，其中前一个部分在 $a$ 中尽量靠左，后一个部分在 $a$ 中尽量靠右，并且两个不相交。

然后就好做了，先对 $b$ 的每一个前缀求出「最右边字符对应在 $a$ 中最靠左的位置」，每一个后缀求出「最左边字符对应在 $a$ 中最靠右的位置」，分别用 $L$ 和 $R$ 数组保存。

最后我们要选出两个断点 $l$ 和 $r$ ，分别代表分成的前后两个部分的右端点和左端点，并且 $L_l<R_r$ ，同时 $r-l$ 要尽量的小。

所以这个怎么求呢？等等， $L$ 和 $R$ 单调递增？

那不是妥妥的双指针吗？

然后这题就做完了，时间复杂度 $O(n)$ 。

代码

#include <bits/stdc++.h>
using namespace std;
int n,m;
string a,b;
int L[100005],R[100005];
int ans=1e9,k1,k2;//最短r-l，以及两个断点的记录 
int main(){
    cin>>a>>b;
    n=a.length(),m=b.length();
    a=" "+a,b=" "+b;
    int r=1;//指针 
    for(int i=1;i<=m;i++){//预处理L数组 
        while(r<=n&&a[p]!=b[i]) r++;
        L[i]=r,r=min(r+1,n+1);
    }
    r=n;
    for(int i=m;i>=1;i--){//预处理R数组 
        while(r>=1&&a[p]!=b[i]) r--;
        R[i]=r,r=max(r-1,0);
    }
    if(L[1]==n+1&&R[m]==0){//这里特判一下，或者在最后特判也行 
        printf("-\n");
        return 0;
    }
    L[0]=0,R[m+1]=n+1;//防越界特判的操作 
    r=1;
    for(int l=0;l<=m;i++){//计算答案，双指针板板 
        if(L[l]==n+1) break;
        r=max(r,l+1);
        while(L[l]>=R[r]){
            r++; 
        }
        if(r-l-1<ans){
            ans=r-l-1,k1=l,k2=r;
        }
    }
    for(int i=1;i<=m;i++){
        if(i<=k1||i>=k2){
            cout<<b[i];
        }
    }
    printf("\n");
    return 0;
}