牛客 109B 好位置 (字符串水题)
2024-10-06 21:08:21
大意: 给定字符串$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");
}
最新文章
- UVALive 4864 Bit Counting --记忆化搜索 / 数位DP?
- mySql 基本语法学习笔记
- HowTo:使用数据流读写消息
- Js分页插件,支持页面跳转
- Java 多线程 并发编程
- 编写服务说明.thrift文件
- Modbus调试利器 Modbus Poll
- Android Intent到底能做些什么
- wordpress函数技巧
- activemq的两种基本通信方式的使用及总结
- CS:APP3e 深入理解计算机系统_3e Attacklab 实验
- [LeetCode] K-th Smallest Prime Fraction 第K小的质分数
- vector用法
- hive 函数 nvl()
- ngClass指令3种使用
- hbase与sqoop的集成
- lua keynote
- javascript实现OOP编程
- KindEditor 上传文件 在Asp.net中的使用
- shell中的条件判断以及与python中的对比