牛客 月月查华华的手机（序列自动机）

月月查华华的手机

https://ac.nowcoder.com/acm/problem/23053
来源：牛客网

题目大意：
给出一个字符串S，然后k次查询，问字符串t是否是s的子序列，是的话输出yes，反之输出no。

因为n和s都是1e6，暴力的话必然会超时，所以用到了序列自动机
就是建立一个next[i][j]数组，记录 i 位置之后【j-‘a’】字母第一次出现的位置然后匹配即可。

自动机的建立

void solve(){//自动机的建立
	n=strlen(s+1);
	for(int i=n;i>=1;i--){
		for(int j=0;j<26;j++) nextt[i-1][j]=nextt[i][j];
		nextt[i-1][s[i]-'a']=i;
	}
}

子串的匹配

bool check(){
	m=strlen(str+1);
	x=0;
	for(int i=1;i<=m;i++){
		x=nextt[x][str[i]-'a'];
		if(!x) return false;
	}
	return true;
}

该题代码：

#include <iostream>
#include <cstdio>
#include<cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#define inf 0x3f3f3f3f
#define ll long long
#define INT 9654234
using namespace std;
const int maxn = 1e6+5;
int n,m,x,t;
char s[maxn],str[maxn];
int nextt[maxn][28];

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

bool check(){
	m=strlen(str+1);
	x=0;
	for(int i=1;i<=m;i++){
		x=nextt[x][str[i]-'a'];
		if(!x) return false;
	}
	return true;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    cin>>s+1;
    solve();
	cin>>t;
	while(t--){
		cin>>str+1;
		if(check()) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}

本文地址：https://blog.csdn.net/weixin_43872264/article/details/107414306