首页 > 代码库 > cf 223B.Two Strings
cf 223B.Two Strings
神奇(%%题解)
题意:判断B串作为A串的子序列,不是不可以把A全部覆盖掉。
这样的话就是判断是不是A[i]最右匹配B的点和最左匹配B的点相交(重合)就好。(不重合的话B自然会空出中间一段,那么肯定不能用B来做A的子序列了)
1 #include<bits/stdc++.h> 2 #define LL long long 3 #define N 100005 4 using namespace std; 5 inline int ra() 6 { 7 int x=0,f=1; char ch=getchar(); 8 while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();} 9 while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();} 10 return x*f; 11 } 12 char s[N<<1],t[N<<1]; 13 int L[N<<1],R[N<<1],last[N<<1]; 14 int main() 15 { 16 scanf("%s%s",s,t); 17 memset(last,-1,sizeof(last)); 18 int j=0,slen=strlen(s),tlen=strlen(t); 19 for (int i=0; i<slen; i++) 20 { 21 L[i]=last[s[i]-‘a‘]; 22 if (j<tlen && s[i]==t[j]) 23 { 24 L[i]=j; 25 j++; 26 } 27 last[s[i]-‘a‘]=L[i]; 28 } 29 memset(last,-1,sizeof(last)); 30 j=tlen-1; 31 for (int i=slen-1; i>=0; i--) 32 { 33 R[i]=last[s[i]-‘a‘]; 34 if (j>=0 && s[i]==t[j]) 35 { 36 R[i]=j; 37 j--; 38 } 39 last[s[i]-‘a‘]=R[i]; 40 } 41 bool ok=1; 42 for (int i=0; i<slen; i++) 43 if (L[i]==-1 || R[i]==-1 || L[i]<R[i]) 44 { 45 ok=0; 46 break; 47 } 48 ok?puts("Yes"):puts("No"); 49 return 0; 50 }
cf 223B.Two Strings
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。