大意: 给定字符串$s1,s2$, 对于$s1$中所有与$s2$相等的子序列$t$, $t$在$s1$中的下标定义为好位置. 求$s1$是否所有位置都是好位置.

显然$s1$的前缀要与$s2$相等, 并且$s2$后缀连续相等的字符要与$s1$的后缀相等, 然后再判断下中间字符是否合法.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <string.h>
#include <bitset>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, P2 = 998244353, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head const int N = 1e6+10;
int n, m, nxt[N][26], f[26];
char s1[N], s2[N]; int main() {
scanf("%s%s", s1+1, s2+1);
n = strlen(s1+1), m = strlen(s2+1);
REP(i,1,m) if (s1[i]!=s2[i]) return puts("No"),0;
for (int i=n,now=m; s2[now]==s2[m]; --now,--i) {
if (s1[i]!=s2[m]) return puts("No"),0;
}
int x = s2[m];
PER(i,1,m) {
if (!f[s2[i]-'a']) f[s2[i]-'a'] = x;
x = s2[i];
}
REP(i,0,25) nxt[n+1][i]=nxt[n+2][i]=n+1;
PER(i,1,n) {
memcpy(nxt[i],nxt[i+1],sizeof nxt[0]);
nxt[i][s1[i]-'a']=i;
}
REP(i,m+1,n) if (s1[i]!=s2[m]) {
if (!f[s1[i]-'a']) return puts("No"),0;
if (nxt[i][f[s1[i]-'a']-'a']>n) return puts("No"),0;
}
puts("Yes");
}

最新文章

  1. UVALive 4864 Bit Counting --记忆化搜索 / 数位DP?
  2. mySql 基本语法学习笔记
  3. HowTo:使用数据流读写消息
  4. Js分页插件,支持页面跳转
  5. Java 多线程 并发编程
  6. 编写服务说明.thrift文件
  7. Modbus调试利器 Modbus Poll
  8. Android Intent到底能做些什么
  9. wordpress函数技巧
  10. activemq的两种基本通信方式的使用及总结
  11. CS:APP3e 深入理解计算机系统_3e Attacklab 实验
  12. [LeetCode] K-th Smallest Prime Fraction 第K小的质分数
  13. vector用法
  14. hive 函数 nvl()
  15. ngClass指令3种使用
  16. hbase与sqoop的集成
  17. lua keynote
  18. javascript实现OOP编程
  19. KindEditor 上传文件 在Asp.net中的使用
  20. shell中的条件判断以及与python中的对比

热门文章

  1. zookeeper系列(九)zookeeper的会话详解
  2. python并发——从线程池获取返回值
  3. token的解码及 判断值不为空的方法
  4. Video Captioning 综述
  5. 性能优化 | JVM与性能优化知识点综合整理
  6. 准确率(Precision)、召回率(Recall)以及综合评价指标(F1-Measure)
  7. PCL中有哪些可用的PointT类型(3)
  8. Hadoop基础之初识大数据与Hadoop
  9. Fluent操作流程&amp;&amp;udf编译
  10. k8s中ipvs和iptables选择