牛客網鏈接

時間限制：C/C++ 2秒，其他語言4秒 空間限制：C/C++ 262144K，其他語言524288K 64bit IO Format:
%lld

題目描述

月月和華華一起去吃飯了。期間華華有事出去了一會兒，沒有帶手機。月月出于人類最單純的好奇心，打開了華華的手機。哇，她看到了一片的QQ推薦好友，似乎華華還沒有瀏覽過。月月頓時醋意大發，出于對好朋友的關心，為了避免華華浪費太多時間和其他網友聊天，她要刪掉一些推薦好友。但是為了不讓華華發現，產生猜疑，破壞了他們的友情，月月決定只刪華華有可能搭訕的推薦好友。
月月熟知華華搭訕的規則。華華想與某個小姐姐搭訕，當且僅當小姐姐的昵稱是他的昵稱的子序列。為了方便，華華和小姐姐的昵稱只由小寫字母構成。為了更加方便，保證小姐姐的昵稱長度不會比華華的長。
現在月月要快速的判斷出哪些推薦好友要刪掉，因為華華快回來了，時間緊迫，月月有點手忙腳亂，所以你趕緊寫個程序幫幫她吧！

輸入描述:

第一行輸入一個字符串A表示華華的昵稱。 第二行輸入一個正整數N表示華華的推薦好友的個數。
接下來N行，每行輸入一個字符串BiB_iBi?表示某個推薦好友的昵稱。

輸出描述:

輸出N行，對于第i個推薦好友，如果華華可能向她搭訕，輸出Yes，否則輸出No。 注意大寫，同時也要注意輸出效率對算法效率的影響。

示例1
輸入

noiauwfaurainairtqltqlmomomo 8 rain air tql ntt xiaobai oiiiooo orzcnzcnznb ooooo

輸出

Yes Yes Yes Yes No Yes No No

備注:

題解：
字符串問題
有兩個解決方法，字典樹和序列自動機都能做（我想到的）
這里就不講字典樹了
序列自動機：
序列自動機就是用一個數組next[i][j]來記錄數組a第i位的字符j在i后第一次出現的坐標。
設串長為n,字符集大小為a，預處理時間復雜度為O(n*a)
序列自動機講解

for(int i=n;i;i--) {for(int j=1;j<=a;j++) next[i-1][j]=next[i][j];next[i-1][s[i]]=i; }

代碼:

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #define forr(n) for(int i=1;i<=n;i++) #define fore(n) for(int j=1;j<=n;j++) using namespace std; const int ma=1000004; char a[ma]; int len; int w=0; int m; bool f=1; int next[ma][30]; int main() {cin>>(a+1);int len=strlen(a+1);for(int i=len;i>=1;i--){for(int j=0;j<=25;j++) next[i-1][j]=next[i][j];next[i-1][a[i]-'a']=i;}cin>>m;char ch=getchar();forr(m){cin>>(a+1);len=strlen(a+1);w=0;f=1;fore(len){w=next[w][a[j]-'a'];if(w==0){f=0;cout<<"N0"<<endl;break;}}if(f!=0)cout<<"Yes"<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的牛客网【每日一题】4月2日 月月查华华的手机的全部內容，希望文章能夠幫你解決所遇到的問題。

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