序列自动机（模板）

给字符串 s 然后 Q 次询问字符串 t 是不是 s 的子序列

序列自动机是用来判断是否是子序列的算法时间复杂度是 $O(len)$

nx[i][j] 数组存的是在 s 中第 i 位后面第一个 j 字母出现的位置

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

const int maxn = 1e6 + 10;
int nx[maxn][30];
string s;

void init() {
    int len = s.length();
    for(int i = 0; i < 26; i ++)
        nx[len][i] = nx[len + 1][i] = len + 1;
    for(int i = len - 1; i >= 1; i --) {
        for(int j = 0; j < 26; j ++)
            nx[i - 1][j] = nx[i][j];
        nx[i - 1][s[i] - 'a'] = i;
    }
}

int main() {
    cin >> s;
    init();
    int Q;
    scanf("%d", &Q);
    while(Q --) {
        string t;
        cin >> t;
        bool flag = true;
        int lt = t.length();
        int st = 0;
        for(int i = 0; i < lt; i ++) {
            st = nx[st][t[i] - 'a'];
            if(st == 0) {
                flag = false;
                break;
            }
        }

        if(flag) printf("YES\n");
        else printf("NO\n");

    }
    return 0;
}

原文链接: https://www.cnblogs.com/zlrrrr/p/10820131.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/294779

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

序列自动机（模板）

相关推荐