鏈接：https://ac.nowcoder.com/acm/contest/392/J
來源：牛客網

題目描述
月月和華華一起去吃飯了。期間華華有事出去了一會兒，沒有帶手機。月月出于人類最單純的好奇心，打開了華華的手機。哇，她看到了一片的QQ推薦好友，似乎華華還沒有瀏覽過。月月頓時醋意大發，出于對好朋友的關心，為了避免華華浪費太多時間和其他網友聊天，她要刪掉一些推薦好友。但是為了不讓華華發現，產生猜疑，破壞了他們的友情，月月決定只刪華華有可能搭訕的推薦好友。
月月熟知華華搭訕的規則。華華想與某個小姐姐搭訕，當且僅當小姐姐的昵稱是他的昵稱的子序列。為了方便，華華和小姐姐的昵稱只由小寫字母構成。為了更加方便，保證小姐姐的昵稱長度不會比華華的長。
現在月月要快速的判斷出哪些推薦好友要刪掉，因為華華快回來了，時間緊迫，月月有點手忙腳亂，所以你趕緊寫個程序幫幫她吧！
輸入描述:
第一行輸入一個字符串A表示華華的昵稱。
第二行輸入一個正整數N表示華華的推薦好友的個數。
接下來N行，每行輸入一個字符串B_iB
i
?
表示某個推薦好友的昵稱。
輸出描述:
輸出N行，對于第i個推薦好友，如果華華可能向她搭訕，輸出Yes，否則輸出No。
注意大寫，同時也要注意輸出效率對算法效率的影響。
示例1
輸入
復制
noiauwfaurainairtqltqlmomomo
8
rain
air
tql
ntt
xiaobai
oiiiooo
orzcnzcnznb
ooooo
輸出
復制
Yes
Yes
Yes
Yes
No
Yes
No
No
備注:
1\le|A|\le10^61≤∣A∣≤10
6
，1\le N\le10^61≤N≤10
6
，1\le\sum_{i=1}^NB_i\le10^61≤∑
i=1
N
?
B
i
?
≤10
6

思路：

本題是序列自動機模板題，

來講解一下序列自動機是一個什么東西，

其實就是一個數組
nxt[ |str| ] [ |S| ] | str | 是字符串的最大長度， 而 | S | 是字符集合的元素個數。

我們對于母穿進行預處理 nxt數組，

nxt[i][j] 表示 第i個位置后面最近的j字符的下標。如果沒有就是0。

獲得的方法很簡單，我們只需要從后向前掃一邊類似dp的方法轉移一下即可。

當一個子串來嘗試匹配為母串的子序列時，只需要順著nxt數組轉移即可，當找不到需要的字符，即匹配到下標為0時（因為母串讀入的時候從下標1開始讀入字符），表示匹配失敗。

返回失敗即可。

細節見代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl using namespace std; typedef long long ll; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;} inline void getInt(int* p); const int maxn=1000010; const int inf=0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/int nxt[maxn][30]; char s[maxn]; int len; void init() {for(int i=len;i>=1;--i){for(int j=0;j<=25;++j){nxt[i-1][j]=nxt[i][j];}nxt[i-1][s[i]-'a']=i;} } char t[maxn]; int main() {//freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);//freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);scanf("%s",s+1);len=strlen(s+1);int q;init();scanf("%d",&q);while(q--){scanf("%s",t);int len1=strlen(t);int isok=1;for(int now=0,i=0;i<len1;++i){now=nxt[now][t[i]-'a'];if(!now){isok=0;break;}}if(isok){puts("Yes");}else{puts("No");}}return 0; }inline void getInt(int* p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}}else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

轉載于:https://www.cnblogs.com/qieqiemin/p/11355472.html

總結

以上是生活随笔為你收集整理的牛客小白月赛12 J月月查华华的手机 （序列自动机模板题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。