Codeforces Round #579 (Div. 3)D（字符串，思维）

#include<bits/stdc++.h>
using namespace std;
char s[200007],t[200007];
int last[200007][27],nxt[200007][27];
int l[200007],r[200007];
int main(){
cin>>s+1>>t+1;
int n=strlen(s+1);
int m=strlen(t+1);
for(int i=1;i<=n;++i){
for(int j=0;j<26;++j)
last[i][j]=last[i-1][j];//i表示当前位置，j表示字母大小，复制当前位置以前最晚出现字母j的位置就是前一格位置以前最晚出现j字母的位置
last[i][s[i]-'a']=i;//更新当前位置以前最晚出现字母s[i]的位置
}
for(int i=n;i;--i){
for(int j=0;j<26;++j)
nxt[i][j]=nxt[i+1][j];//复制当前位置以后最早出现字母j的位置就是前一格位置以前最早出现字母j的位置
nxt[i][s[i]-'a']=i;//更新当前位置以后最早出现字母s[i]的位置
}
int now=1;
l[0]=1;
for(int i=1;i<=m;++i){
now=nxt[now][t[i]-'a']+1;//now表示now位置以后最早出现字母t[i]的位置，保证该位置以后还能有剩余的t字符串i+1~m
l[i]=now;//更新i位置左端点的值为now
}
now=n;
r[m+1]=n;
for(int i=m;i;--i){
now=last[now][t[i]-'a']-1;//now表示now位置以前最晚出现字母t[i]的位置，保证该位置以前还能有剩余的t字符串1~i-1
r[i]=now;//更新i位置右端点的值为now
}
int ans=0;
for(int i=0;i<=m;++i)
ans=max(r[i+1]-l[i]+1,ans);//更新答案为字母t[i+1]最晚出现的位置减去字母t[i]最早出现的位置+1
cout<<ans;
return 0;
}

巴特西

Codeforces Round #579 (Div. 3)D（字符串，思维）

最新文章

热门文章