序列自动机
今天刚学了序列自动机感觉挺妙的； 这个就是给你一个母串，再给一下子串让你判断哪些子串是他的子串 这时候我们可以先对母串进行预处理一下： 用一个二维数来记录第i个位置后面的每个字母出现的第一个位置，dp[i][j]表示第 i 个位置以后字母 j 第一次出现的位置；当这个预处理结束后我们在查找的时候就可以找到这个字母的位置后再从这个位置查找下个字符这样一直跳着来查询就可以很快的查找结束了 预处理 我们可以从后向前慢慢的遍历这样一个循环就好了，但是注意存储的时候需要从第一个数开始，初始化的时候把数组初始化为 -1 ；比如 第 i+1 个字符是 a 那么dp[i][a]=i+1;其他的字符都是dp[i][b]=dp[i+1][b]; 查找 i=0； 直接从dp[i][x] (x为需要判断的子串的第一个字符);然后每次更新 i 的位置，顺序的遍历需要判断的子串的每个字符就可以了，一旦遇到 -1 就结束说明不可能是；
下面看个例题吧 子串查询：题目链接 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld 题目描述 给出一个长度为n的字符串s和q个查询。对于每一个查询，会输入一个字符串t，你需要判断这个字符串t是不是s的子串。子串的定义就是存在任意下标a<b<c<d<e，那么”s[a]s[b]s[c]s[d]s[e]”就构成s的一个子串。如”abc”的子串有”a”、”b”、”c”、”ab”、”ac”、”bc”、”abc”。 输入描述: 第一行两个数n，q。1<=n，q<=1e5。
第二行一个长度为n的字符串s,所有字符都为小写拉丁字符。
接下来q行每行一个字符串t。1<=|t|<=50。 输出描述: 对于每个查询，如果t是s的字串，输出”YES”,否则输出”NO”。每个答案占一行。 输入
8 4
ababcbaa
abac
accb
aaaa
abcba输出
YES
NO
YES
YES#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
char a[maxn],b[maxn];
int n,m;
int dp[maxn][30];
//构建动态的数组
void build()
{
memset(dp,-1,sizeof dp);//初始化的值只要不可能出现就行
//记录这个位置以后最先出现的字符
for(int j=n-1;j>=0;j--)//从倒数二个位置开始遍历
{
for(int i=0;i<26;i++)// 判断这个位置的下个字符 i 的位置
{
if(a[j+1]-'a'==i)// 如果下个字符是 i 就更新位置
dp[j][i]=j+1;
else dp[j][i]=dp[j+1][i];// 如果不等就 和上个位置一样
}
}
}
int main()
{
//因为进行预处理的时候是这个位置以后最先出现的字符
//所以不能从0开始存字符 ，要从1开始
scanf("%d%d%s",&n,&m,a+1);
build();
while(m--)
{
scanf("%s",b);
int le=strlen(b);
bool flag=0;
int j=0;//初始化 j=0；
for(int i=0;i<le;i++)//顺序遍历子串的每个字符
{
// 如果等于-1就结束
if(dp[j][b[i]-'a']==-1){
flag=1;
break;
}
j=dp[j][b[i]-'a'];//更新j的位置
}
puts(flag?"NO":"YES");
}
return 0;
}腾讯云开发者
