20200402 月月查华华的手机

下载pdf，获得更好的阅读体验。

提取码：06ez

问题简述

给出字符串 ，查询 是否为 的子串，询问 次。

查询 是否为 的子串可以用序列自动机完成。

序列自动机

在 JSOI2019SC 听过这个科技，现在又查了几个博客复习了一下。

序列自动机的构建

序列自动机的核心在于 数组（由于其他一些字符串算法，常习惯写为 。

代表位置 后字符 第一次出现的位置。

图片说明

当从位置 移动到位置 时，显然只有一个字符的 值发生变化。

代码：

void Build(void) {
    n = strlen(s + 1);
    for(int i = n; i >= 1; i--) {
        for(int j = 0; j < 26; j++) fail[i - 1][j] = fail[i][j];
        fail[i - 1][s[i] - 'a'] = i;

    }
}

序列自动机的查找

从头向后移动匹配，一旦失配，直接失败。

bool check(void) {
    int m = strlen(t + 1), pos = 0;
    for(int i = 1; i <= m; i++) {
        pos = fail[pos][t[i] - 'a'];
        if(!pos) return false;
    }
    return true;
}

题解

不难发现，这个题就是个模板题，粘贴好模板就行了。

Code

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

const int maxs = 1000000 + 7;

int n, T;
char s[maxs], t[maxs];
int fail[maxs][28];

void Build(void) {
    n = strlen(s + 1);
    for(int i = n; i >= 1; i--) {
        for(int j = 0; j < 26; j++) fail[i - 1][j] = fail[i][j];
        fail[i - 1][s[i] - 'a'] = i;

    }
}

bool check(void) {
    int m = strlen(t + 1), pos = 0;
    for(int i = 1; i <= m; i++) {
        pos = fail[pos][t[i] - 'a'];
        if(!pos) return false;
    }
    return true;
}

int main(void) {
    scanf("%s", s + 1);
    Build();
    scanf("%d", &T);
    while(T--) {
        scanf("%s", t + 1);
        if(check()) puts("Yes");
        else puts("No");
    }
    return 0;
}