【每日一题】字符串枚举优化

枚举优化

https://ac.nowcoder.com/acm/problem/23053
这题目描述这么费劲干啥啊==''==
题目：给定序列s,t,判断t是否是s的子序列
思想可以参考KMP利用next数组匹配子串，我们维护一个next[i][a,b,c……z]来表示第i个字母后面的第一个a,b……字母位置；注意：比如s中有两个以上a字母，匹配时候肯定是选前面的，因为前面的如果匹配不了t，后面的就更不可能。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int nex[maxn][26];
int last[26]={0};
void pre(string s)
{
    memset(last,-1,sizeof(last));
    int len=s.size();
    for(int i=len-1;i>=0;--i){
        int c=s[i]-'a';
        //cout<<c<<endl;
        memcpy(nex[i],last,sizeof(int)*26);
        last[c]=i;
    }
    return;
}

int main(){
    string s;cin>>s;
    int n;cin>>n;
    pre(s);
    for(int i=0;i<n;++i){
        bool ok=false;
        string t;cin>>t;
        int len=t.size();
        int ne=last[t[0]-'a'];
        for(int i=1;i<len;++i){
            ne=nex[ne][t[i]-'a'];
            //cout<<t[i]<<" "<<ne<<endl;
            if(ne==-1) {
                cout<<"No"<<endl;
                ok=true;
                break;
            }
        }
        if(!ok)cout<<"Yes"<<endl;
    }
}