D1. Remove the Substring (从easy到hard)

\(对于easy版本\)

\(直接枚举删掉的区间[l,r]判断是否存在t子串\)

\(这个很简单很暴力\)

#include <bits/stdc++.h>
using namespace std;
const int maxn=209;
char s[maxn],t[maxn];
int ans;
bool isok(int l,int r)
{
    int x=1;
    for(int i=1;i<=strlen(s+1);i++)
    {
        if(i>=l&&i<=r)    continue;
        if(t[x]==s[i])  x++;
        if(x==strlen(t+1)+1)    return true;
    }
    return false;
}
int main()
{
    cin>>(s+1)>>(t+1);
    for(int i=1;i<=strlen(s+1);i++)
    for(int j=i;j<=strlen(s+1);j++)
        if(isok(i,j))   ans=max(ans,j-i+1);
    cout<<ans;
}

\(\color{red}hard版本\)

\(我们知道,区间最大有两种情况\)

\(一、首字符出现最晚,此时删掉[1,首字符)\)

\(末字符出现最早,此时删掉(末字符,n](n是s串长度)\)

\(二、当最快匹配到i位置时,下一个匹配的字母使其最远为j,此时可删掉(i,j)\)

\(\color{Red}这些都不难想,包括最快匹配到i字符的位置\)

\(最快,所以我们一个字符一个字符匹配,相同就往后匹配\)

\(那如何知道下一个字母最晚能在哪里匹配呢?\)

\(\color{orange}我们只需要倒着求一遍倒着的t串最快匹配位置即可\)

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
char s[maxn],t[maxn];
int pre[maxn],last[maxn],top1,top2,ls,lt,ans;
void isok1()
{
    int x=1;
    for(int i=1;i<=ls;i++)
    {
        if(s[i]==t[x])  pre[x++]=i;
        if(x>lt) return;
    }
}
void isok2()
{
    int x=lt;
    for(int i=ls;i>=1;i--)
    {
        if(s[i]==t[x])  last[x--]=i;
        if(x<1)  return;
    }
}
int main()
{
    cin>>(s+1)>>(t+1);
    ls=strlen(s+1),lt=strlen(t+1);
    isok1();isok2();
    ans=max(last[1]-1,ls-pre[lt]);
    for(int i=1;i<lt;i++)
        ans=max(ans,last[i+1]-pre[i]-1);
    cout<<ans;
}