链接

点击跳转

题解

对于每个字符计算$pr{e}_i$表示拿前缀$s[1...i]$去匹配$x$串的前缀，$s[i]$这个字符能匹配到的$x$中最靠后的字符

$su{f}_i$同理，表示拿后缀$s[i...n]$去匹配$x$串的后缀，$s[i]$这个字符能匹配到的$x$中最靠前的字符

最后只需要判断$su{f}_i\le pr{e}_i$就行了

代码

#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define iinf 0x3f3f3f3f #define linf (1ll<<60) #define eps 1e-8 #define maxn 1000010 #define maxe 1000010 #define cl(x) memset(x,0,sizeof(x)) #define rep(i,a,b) for(i=a;i<=b;i++) #define drep(i,a,b) for(i=a;i>=b;i--) #define em(x) emplace(x) #define emb(x) emplace_back(x) #define emf(x) emplace_front(x) #define fi first #define se second #define de(x) cerr<<#x<<" = "<<x<<endl using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; ll read(ll x=0) { ll c, f(1); for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f; for(;isdigit(c);c=getchar())x=x*10+c-0x30; return f*x; } char s[maxn], t[maxn]; ll pre[maxn], suf[maxn], last[300]; int main() { ll i, n, m; scanf("%s%s",s+1,t+1); n=strlen(s+1), m=strlen(t+1); ll j=0; rep(i,1,n) { if(s[i]==t[j+1])j++, last[t[j]]=j; pre[i]=last[s[i]]; } j=m+1; rep(i,'a','z')last[i]=m+1; drep(i,n,1) { if(s[i]==t[j-1])j--, last[t[j]]=j; suf[i]=last[s[i]]; } rep(i,1,n) { if(suf[i]>pre[i]) { printf("No"); return 0; } } printf("Yes"); return 0; }