题解：CF1203D1 Remove the Substring (easy version)

LHM_zs · 2025-03-08 13:20:06 · 题解

题目大意

给定两个字符串 s 和 t ，其中 t 是 s 的子序列。要求删除 s 中的一个连续子串，使得删除后的 s 仍包含 t 作为子序列。求可删除的最长连续子串的长度。

解题思路

预处理左匹配位置：

构造数组 left，其中 left_i 表示 t 的前 i 个字符在 s 中最左匹配的结束位置。

预处理右匹配位置：

构造数组 right，其中 right_i 表示 t 的后 i 个字符在 s 中最右匹配的起始位置。

计算最大间隙：

遍历所有可能的间隙 i，计算 right_i - left_i- 1 的最大值，即为可删除的最长子串长度。

附上代码

#include<bits/stdc++.h>
using namespace std;
string s,t;
int left[1000005],right[1000005];
int main(){
    cin>>s>>t;
    memset(left,-1,sizeof(left));
    memset(right,s.size(),sizeof(right));
    int n=t.size();
    left[0]=-1;
    for(int i=1;i<=n;++i){
        char c=t[i-1];
        int pos=left[i-1]+1;
        while(pos<s.size()&&s[pos]!=c){
            pos++;
        }
        left[i]=pos;
    }
    right[n]=s.size();
    for(int i=n-1;i>=0;--i){
        char c=t[i];
        int pos=right[i+1]-1;
        while(pos>=0&&s[pos]!=c){
            pos--;
        }
        right[i]=pos;
    }
    int maxx=0;
    for(int i=0;i<=n;++i){
        int current=right[i]-left[i]-1;
        if(current>maxx){
            maxx=current;
        }
    }
    cout<<maxx;
    return 0;
}