序列自动机

给出一个字符串s1，再给你n个子字符串s2，每次回答s2是否为s1的子序列
next[i][j]表示在位置i后面第一个字符j所在的位置,预处理出next数组的复杂度为log(N*26)
每次询问是log(M)M是每次询问的字符串长度

此处的子串是在主串是非连续的

序列自动机模板

传送门

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+100;

int Next[maxn][30], n, len;
char first[maxn], second[maxn];

void init() {
    scanf("%s", first+1);
    len = int(strlen(first+1));

    for(int i=len;i>=1;i--) {
        if(i == len){
            for(int j=0;j<30;j++) {
                Next[i][j] = len+1;
            }
        }
        for(int j=0;j<30;j++) {
            Next[i-1][j] = Next[i][j];
        }
        Next[i-1][first[i] - 'a'] = i;
    }
}

bool find() {
    int pos = 0;
    int len2 = int(strlen(second));
    for(int i=0;i<len2;i++) {
        pos = Next[pos][second[i]-'a'];
        if(pos > len) return false;
    }
    return true;
}

int main() {
//    freopen("1.in", "r", stdin);
    init();

    scanf("%d", &n);
    while(n--) {
        scanf("%s", second);
        if(find()) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }

    return 0;
}

string函数求自动机

时间复杂度高于序列自动机,
对于一个查找时间复杂度为O(N*M)
N是主串长度,M是子串长度

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n,q,i,pos,f;
string s,a;//主串s,子串a
int main(){
    cin>>n>>q>>s;
    while(q--){
        cin>>a,pos=0,f=1;
        for(i=0;i<a.length()&&f;i++){//遍历子串的所有字母
            auto it=s.find(a[i],pos);//在主串中找子串的字母第一次出现的位置
            //printf("%d\n",it);
            if(it==s.npos)f=0;//npos表示不存在
            else pos=it+1;
        }
        puts(f?"YES":"NO");
    }
}

序列自动机

原文：https://www.cnblogs.com/Emcikem/p/11484848.html