codeforces 1203D2 Remove the Substring (hard version)

这题还挺难得，当时比赛看了题没想法后，做完E再回来做才过掉，比赛的时候是用二分以后扫一遍判断的，比赛后学习了O(n)做法，觉得更加好一些。

s从前往后匹配t，得到t的每一个位置在s中的位置pre[1...tlen]，从后往前匹配t，得到last[1...tlen]

那么答案其实就是删除中间最长的一段，是的pre和last能够连起来。

二分的话，先让二分出来的要删除的长度为mid段在slen-mid+1到slen这里，然后看从前往后能跑匹配到t 的前id位，然后将要删除的段不断前移，于是id不断减少，再从后往前匹配tlen，lastid=tlen，lastid不断减小，等到匹配上的时候，这个mid就是可行的

#include<bits/stdc++.h>
#define maxl 200010
using namespace std;
int n,slen,tlen,ans;
int pre[maxl],last[maxl];
char s[maxl],t[maxl];
inline void prework()
{
scanf("%s%s",s+1,t+1);
slen=strlen(s+1);
tlen=strlen(t+1);
}
inline void mainwork()
{
int id=1;
for(int i=1;i<=slen;i++)
if(s[i]==t[id])
{
pre[id]=i;
id++;
if(id>tlen) break;
}
id=tlen;
for(int i=slen;i>=1;i--)
if(s[i]==t[id])
{
last[id]=i;
id--;
if(id<=0) break;
}
ans=max(slen-pre[tlen],last[1]-1);
for(int i=1;i<tlen;i++)
ans=max(ans,last[i+1]-pre[i]-1);
}
inline void print()
{
printf("%d",ans);
}
int main()
{
prework();
mainwork();
print();
return 0;
}

#include<bits/stdc++.h>
#define maxl 300010
using namespace std;
int n,m,ans,slen,tlen;
int a[maxl],nxt[maxl],frm[maxl],in[maxl];
char s[maxl],t[maxl];
inline void prework()
{
scanf("%s%s",s+1,t+1);
slen=strlen(s+1);
tlen=strlen(t+1);
}
inline bool jug(int mid)
{
for(int i=1;i<=slen;i++)
nxt[i]=frm[i]=in[i]=0;
int id=1,last=0;
for(int i=1;i<=slen-mid;i++)
{
if(t[id]==s[i])
{
frm[i]=last;
in[i]=id;
id++;last=i;
}
if(id>tlen)
break;
}
if(id>tlen)
return true;
id--;
int st=slen-mid+1,lastid=tlen;
for(int i=st-1;i>=1;i--)
{
if(in[i]>0)
id--;
if(s[i+mid]==t[lastid])
lastid--;
if(lastid==id)
return true;
}
return false;
}
inline void mainwork()
{
int l=0,r=slen,mid;
while(l+1<r)
{
mid=(l+r)>>1;
if(jug(mid))
l=mid;
else
r=mid;
}
if(jug(r))
ans=r;
else
ans=r-1;
}
inline void print()
{
printf("%d",ans);
}
int main()
{
int t=1;
//scanf("%d",&t);
for(int i=1;i<=t;i++)
{
prework();
mainwork();
print();
}
return 0;
}

最后

以上就是羞涩秋天为你收集整理的codeforces 1203D2 Remove the Substring (hard version)的全部内容，希望文章能够帮你解决codeforces 1203D2 Remove the Substring (hard version)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。