字符串子序列匹配问题
题目给你长度为n的字符串L,给你q个长度为0~m的字符串b,让你判断每一个b是否是字符串L的子序列。(L和b长度小于1e5)
例题:Long Long Ago
有三种做法。最后一种能过。
一、最长公共子序列
比赛时看到这题,因为刚看了dp,就想用LCS来做,求每一个b与字符串L的最长公共子序列的长度,如果等于b的长度,就能判断为对。空间虽然可以用滚动数组优化,时间复杂度为O(n*m),过不了。
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define d(x) cout << (x) << endl
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
const int M = 1e3 + 10;
int m, n;
int dp[N];
int lastdp[N];
int ans;
void g()
{
for (int i = 0; i <= n; i++){
lastdp[i] = dp[i];
}
ans = dp[n];
memset(dp, 0, sizeof(dp));
}
int common(char a[], char b[])
{
memset(dp, 0, sizeof(dp));
memset(lastdp, 0, sizeof(lastdp));
for (int i = 1; i <= m; i++) { //复杂度为 n * m
for (int j = 1; j <= n; j++) {
// if(a[i-1] == b[j-1]){
// dp[i][j] = dp[i - 1][j - 1] + 1;
// }else{
// dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
// }
if(a[i-1] == b[j-1]){
dp[j] = lastdp[j - 1] + 1;
}else{
dp[j] = max(dp[j - 1], lastdp[j]);
}
}
g(); //更新数组滚动
}
return ans;
}
int main()
{
char a[N];
char b[N];
scanf("%s", a);
m = strlen(a);
int t;
scanf("%d", &t);
while(t--){
scanf("%s", b);
n = strlen(b);
if(n > m){
printf("No\n");
continue;
}
if(common(a, b) == n){
printf("Yes\n");
}else{
printf("No\n");
}
}
return 0;
}
二、暴力
看到好多人过了,就想用暴力。思路很简单,遍历b字符串的每一位,在L字符串里找,找到了就看下一位,要注意在L字符串里找时每次的位置都要比上一次靠后。复杂度还是O(n*m), 虽然还是过不了,我觉得应该比上面的方法快一点,毕竟第二个循环不用每次都遍历。
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define d(x) cout << (x) << endl
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
char a[N];
char b[N];
int t, pos, _;
int main()
{
scanf("%s", &a);
for (scanf("%d", &_); _; _--)
{
scanf("%s", b);
int flag = 0;
pos = -1;
for (int i = 0; i < strlen(b); i++){
if(pos == strlen(a)-1){ //如果找的位置没有比上一次靠后
flag = 1;
}
if(flag == 1){ //没有找到,或者没有比上一次靠后就退出
break;
}
t = pos; //存上一次的位置
flag = 1;
for (int j = pos + 1; j < strlen(a); j++){ //从上一次后面的位置开始找
if(a[j] == b[i]){
flag = 0;
pos = j;
break;
}
}
}
if(flag == 0){
printf("Yes\n");
}else{
printf("No\n");
}
}
return 0;
}
三、二分找
我们想一下上一次的暴力,第二重循环是在L中找字符串。如果把L字符串中每一位的位置用vector存一下,
举个例子,L = “abbc"; 那么a[‘a’] = {0}, a[‘b’] = {1, 2}, a[‘c’] = {3};
这样每一种字符出现的位置按顺序存起来,第二重循环就可以简化为二分地查,等于少了一个循环,复杂度O(n*log(m)), 就能过了。
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define d(x) cout << (x) << endl
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e4 + 10;
vector<int> a[30];
int n, pos;
int main(){
ios::sync_with_stdio(0);
string L;
cin >> L;
for(int i = 0; i < L.size(); i++){
a[L[i] - 'a'].push_back(i);
}
for (cin >> n; n; n--){
string b;
cin >> b;
bool flag = false;
int len = 0; //代表每次从L的哪一位开始找
for(int i = 0; i < b.size(); i++){
// 如果要找的那个字符没有出现过
// 或者len比那个字符出现的最大位置还大
if(a[b[i] - 'a'].empty() || *(a[b[i] - 'a'].end() - 1) < len){
flag = true;
break;
}
len = *(lower_bound(a[b[i] - 'a'].begin(), a[b[i] - 'a'].end(), len)) + 1;
}
if(flag)
cout << "No\n";
else
cout << "Yes\n";
}
return 0;
}