题解 | 关于子序列的查找问题 #

$[子序列]$

第一道题目：给你一个长度为 $n$ 的字符串 $s$ ，然后判断 $m$ 个字符串 $t_{i}$ 是否是 $s$ 的子序列。https://ac.nowcoder.com/acm/contest/1083/B

以这道题目介绍基本的模板，首先以字符串 $s$ 建立 $next[i][j]$ 数组， $i$ 表示： $s$ 中第 $i$ 个字符； $j$ 表示：从 $i$ 个字符向后面走最近的字符 $('a'+j)$ 的位置

$build$ 函数：

初始化所有的 $nex[i][j]$ 都为无穷大，表示后面没有 $('a'+j)$ ；

注意 $s$ 的下标从 $0$ 开始，我习惯从 $1$ 开始，所以前面加上空白符号后， $len\_s$ 需要减去 $1$

注意初始化时，下标必须从 $0$ 到 $len\_s$ 完整覆盖

后面的转移方程很好理解，只需要注意是逆序更新的，因为从后向前推就是为了找‘第 $i$ 个字符后面最近的位置。

const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int nex[N][26];

void build(string s){
    s = " " + s;
    int len_s = (int)s.size() - 1;
    for(int i = 0; i <= len_s; i ++){
        for(int j = 0; j < 26; j ++) nex[i][j] = inf;
    }
    for(int len_s; i >= 1; i --){
        for(int j = 0; j < 26; j ++) nex[i - 1][j] = nex[i][j];
        nex[i - 1][s[i] - 'a'] = i;
    }
}

判断字符串 $t_{i}$ 是否是 $s$ 的子序列，有了 $next[i][j]$ 数组就十分方便了：

注意 $now\_pos = 0$ 为初始位置，不是 $1$ ，原因是在 $build$ 函数逆序倒推的过程中，最后一步当 $len\_s=1$ 时， $nex[i-1][s[i]-'a']=i$ ， $i-1=0$ .

bool check(string t){
    t = " " + t;
    int len_t = (int)t.size() - 1;
    int now_pos = 0;
    for(int i = 1; i <= len_t; i ++){
        if(nex[now_pos][t[i] - 'a']  == inf) return false;
        now_pos = nex[now_pos][t[i] - 'a'];
    }
    return true;
}

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int n, m;
int nex[N][26];
string s, t;

void build(){
    int len_s = (int)s.size() - 1;
    for(int i = 0; i <= len_s; i ++){
        for(int j = 0; j < 26; j ++) nex[i][j] = inf;
    }
    for(int i = len_s; i >= 1; i --){
        for(int j = 0; j < 26; j ++) nex[i - 1][j] = nex[i][j];
        nex[i - 1][s[i] - 'a'] = i;
    }
}

void work(){
    int len_t = (int)t.size() - 1;
    int now_pos = 0;
    for(int i = 1; i <= len_t; i ++){
        if(nex[now_pos][t[i] - 'a'] == inf){
            cout << "NO" << endl;
            return ;
        }
        now_pos = nex[now_pos][t[i] - 'a']; 
    }
    cout << "YES" << endl;
}
signed main(){
    HelloWorld;
    
    cin >> n >> m;
    cin >> s;
    s = " " + s;
    build();

    for(int i = 1; i <= m; i ++){
        cin >> t;
        t = " " + t;
        work();
    }
    return 0;
}

时间复杂度为 $O(26\times n+\sum_{}^{}{len\_t})$

第二道题目：给出两个字符串 $s$ 与 $t$ ，然后问不断从字符串 $s$ 中选取子序列拼凑成 $t$ ，最小需要选取多少次，或者直接输出 $-1$ 表示不可能拼凑成 $t$ 。https://codeforces.com/contest/1295/problem/C

$build$ 函数一模一样

$ans$ 得初始化为1，表示我一开始进行一次拼凑
如果 $ans\_pos=len\_s$ ，表示我已经在 $s$ 中循环完了，那么就需要开始下一次的拼凑，所以 $ans++,now\_pos=0$
如果 $nex[now\_pos][t[i]-'a']=inf$ ，表示在字符串 $s$ 中， $now\_pos$ 后面没有 $t[i]-'a'$ 了，所以就需要进行下一次拼凑，所以 $ans++,now\_pos=0$
但如果 $nex[now\_pos][t[i]-'a']=inf$ 并且， $nex\_pos=0$ ，那么从一开始的位置都没有 $t[i]-'a'$ ，那只能说明不能拼凑出 $t$ ，直接输出 $-1$ ，并且 $return$

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;

int nex[N][26];
string s, t;

void build(){
    int len_s = (int)s.size() - 1;
    for(int i = 0; i <= len_s; i ++){
        for(int j = 0; j < 26; j ++) nex[i][j] = inf;
    }
    for(int i = len_s; i >= 1; i --){
        for(int j = 0; j < 26; j ++) nex[i - 1][j] = nex[i][j];
        nex[i - 1][s[i] - 'a'] = i;
    }
}

void work(){
    int ans = 1, now_pos = 0;
    int len_s = (int)s.size() - 1;
    int len_t = (int)t.size() - 1;
    for(int i = 1; i <= len_t; i ++){
        if(now_pos == len_s || nex[now_pos][t[i] - 'a'] == inf){
            ans ++;
            now_pos = 0;
        }
        if(nex[now_pos][t[i] - 'a'] == inf && now_pos == 0){
            ans = inf;
            break;
        }
        now_pos = nex[now_pos][t[i] - 'a'];
    } 
    if(ans >= inf) cout << "-1" << endl;
    else cout << ans << endl;
}
void solve(){
    cin >> s >> t;
    s = " " + s;
    t = " " + t;
    build();
    work();
}
signed main(){
    HelloWorld;
    
    int tt; cin >> tt;
    while(tt --) solve();
    return 0;
}

第三道题目：这里有 $n$ 个字符串 $s_{i}$ ，和 $m$ 个字符串 $t_{i}$ ，回答每一个 $s_{i}$ 中有多少个 $t_{i}$ 是它的子序列。https://ac.nowcoder.com/acm/problem/20859
如果会了前面两道题目，只需要注意字符包含大小写字母，所以适当修改一下就行了。

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 110;
const int inf = 0x3f3f3f3f;
int nex[N][52];
int n, m;

void build(string s){
    int len_s = (int)s.size() - 1;
    for(int i = 0; i <= len_s; i ++){
        for(int j = 0; j < 52; j ++) nex[i][j] = inf;
    }
    for(int i = len_s; i >= 1; i --){
        for(int j = 0; j < 52; j ++) nex[i - 1][j] = nex[i][j];
        if('a' <= s[i] && s[i] <= 'z') nex[i - 1][s[i] - 'a'] = i;
        else nex[i - 1][(s[i] - 'A') + 26] = i;
    }
}

bool work(string t){
    int len_t = (int)t.size() - 1;
    int now_pos = 0;
    for(int i = 1; i <= len_t; i ++){
        if('a' <= t[i] && t[i] <= 'z'){
            if(nex[now_pos][t[i] - 'a'] == inf) return false;
            now_pos = nex[now_pos][t[i] - 'a'];
        }
        else{
            if(nex[now_pos][(t[i] - 'A') + 26] == inf) return false;
            now_pos = nex[now_pos][(t[i] - 'A') + 26];
        }
    }
    return true;
}
signed main(){
    HelloWorld;
    
    cin >> n >> m;
    vector<string> s(n + 1), t(m + 1);
    for(int i = 1; i <= n; i ++) cin >> s[i], s[i] = " " + s[i];
    for(int i = 1; i <= m; i ++) cin >> t[i], t[i] = " " + t[i];
    for(int i = 1; i <= n; i ++){
        build(s[i]);
        int ans = 0;    
        for(int j = 1; j <= m; j ++){
            if(work(t[j])) ans ++;
        }
        cout << ans << endl;
    }
    return 0;
}