题解：CF1203D1 Remove the Substring (easy version)

题目大意

给定两个字符串

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

的最大值，即为可删除的最长子串长度。

附上代码

CPP

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

题解：CF1203D1 Remove the Substring (easy version)

文章操作

题目大意

解题思路

预处理左匹配位置：

预处理右匹配位置：

计算最大间隙：

附上代码

相关推荐

评论

题解：CF1203D1 Remove the Substring (easy version)