cf 223B.Two Strings
2024-10-01 06:18:52
神奇(%%题解)
题意:判断B串作为A串的子序列,不是不可以把A全部覆盖掉。
这样的话就是判断是不是A[i]最右匹配B的点和最左匹配B的点相交(重合)就好。(不重合的话B自然会空出中间一段,那么肯定不能用B来做A的子序列了)
#include<bits/stdc++.h>
#define LL long long
#define N 100005
using namespace std;
inline int ra()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
char s[N<<],t[N<<];
int L[N<<],R[N<<],last[N<<];
int main()
{
scanf("%s%s",s,t);
memset(last,-,sizeof(last));
int j=,slen=strlen(s),tlen=strlen(t);
for (int i=; i<slen; i++)
{
L[i]=last[s[i]-'a'];
if (j<tlen && s[i]==t[j])
{
L[i]=j;
j++;
}
last[s[i]-'a']=L[i];
}
memset(last,-,sizeof(last));
j=tlen-;
for (int i=slen-; i>=; i--)
{
R[i]=last[s[i]-'a'];
if (j>= && s[i]==t[j])
{
R[i]=j;
j--;
}
last[s[i]-'a']=R[i];
}
bool ok=;
for (int i=; i<slen; i++)
if (L[i]==- || R[i]==- || L[i]<R[i])
{
ok=;
break;
}
ok?puts("Yes"):puts("No");
return ;
}
最新文章
- 学习笔记:delphi多线程知识
- 你一无所知的CSS
- 快消品销售管理系统,PDA销售管理系统,销售拜访PDA,进销存管理PDA系统 移动扫描打印开单POS
- php基础09:提取表单数据
- 在桌面chrome中调试android设备中的web页面
- 用HTML5 Canvas 做擦除及扩散效果
- xxx.java: Recompile with -Xlint:deprecation for details
- iOS 关于UITableView的黑科技
- linux字符集介绍及解决中文乱码实战
- hosts管理工具1.0发布了。。。。
- Hadoop大数据部署
- Java_判断文件是否写入完成
- springboot13 发布和监听事件
- ROS 可视化(一): 发布PointCloud2点云数据到Rviz
- some working learning总结学习(二)
- maven 详解二
- MVC001之mvcpager简单分页
- ASP.NET中修改从数据库获取的datatable中的值
- layer关闭当前窗口并刷新父窗口
- UVM序列篇之一:新手上路