好位置

题意

来源:牛客练习赛17B

给出两个串s和x

定义s中的某一位i为好的位置,当且仅当存在s的子序列 满足y=x且存在j使得i=kj成立。

问s中是否所有的位置都是好的位置。

输入描述:

一行两个字符串s,x,这两个串均由小写字母构成。

1 <= |s|, |x| <= 200000

输出描述:

Yes表示是。

No表示不是。

分析

dp[i] 表示以s[i]结尾的最长匹配长度。

然后可以发现这个dp数组满足一个性质,所有的上升子序列长度都为x.size()

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//ybmj
#include<bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 2e5+5;
int dp[maxn];
int last[200];



int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
std::ios::sync_with_stdio(false);
string s,x;
while(cin >> s >> x){
int now = 0;
dp[0] = 0;
clr(last,-1);
bool flag= true;
for(int i=1;i<=s.size();i++){
if(now < x.size() && s[i - 1] == x[now]){
now ++ ;
dp[i] = dp[i-1] + 1;
last[s[i-1] - 'a'] = dp[i];
}
else{
dp[i] = last[s[i-1] - 'a'];
if(dp[i] == -1){
flag = false;
break;
}
}
}
if(!flag){
cout << "No" << endl;
continue;
}
int val = 0;
for(int i=1;i<=s.size();i++){
if(dp[i] < val) val = dp[i];
else if(dp[i] == val + 1) val++;
}
if(val == x.size()) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
Thank you for your support!