题目:
图片说明
题目大意:给出一个字符串,我们假设它为a,然后该给出若干字符串b,请你判断b串是否为a串的子序列串。(注意这里的子序列串是指不一定连续的串)
本人只是把题解老师的思路用我自己的想法整理一遍,希望对大家有用。
首先,这题暴力解法肯定是被T掉的。其实最主要的还是对母串进行预处理,按照题解老师的思路,我们要对母串进行如下处理:将每个字符后面的a,b,c...z的第一次出现的位置记录在数组里面,我们这里用temp二维数组存储。如果没有出现该字符,则用-1代替。
接下来,我们看如何实现预处理:

void deal(){
    memset(ans,-1,sizeof(ans));
    int len=a.length();
    for(int i=len-1;i>=0;i--){  //从后往前遍历每个位置 
        for(int k=0;k<26;k++){   
            temp[i][k]=ans[k];  //将该位置后面的出现的从a-z的第一个位置记录下来
        }
        ans[a[i]-'a']=i;  
    }
}

首先,将ans数组都置为-1,ans数组的作用先不管,后面就会理解。我们将母串从后往前进行遍历,在到达每一个字符的时候,我们要记录下当前字符后面从a-z第一次出现时的位置。同时,还要对ans进行更新,然后再继续往前进行遍历,这样我们再遍历前一个位置的时候,ans数组里面装的元素就可以确保为正在遍历的字符后面从a-z字符第一次出现的位置,然后继续将ans数组的值赋给temp数组和更新ans数组即可。所以我们的ans数组的作用就是动态地记录当前遍历的字符后面从a-z字符的第一次出现的位置。
我们在完成预处理后,我们的ans数组里面的元素就是a串中的从a-z字符第一次出现的位置了。(如果有的话,没有就是-1)
进行完预处理后,我们就要对每个要判断的字符串b进行判断了,判断函数如下:

bool judge(){
    int len1=a.length(),len2=b.length();
    int i=ans[b[0]-'a'];  //首先要找到字符串b中的第一个字符在字符串a中的位置存入i
    if(i==-1)  return 0;  //如果连第一个字符都找不到,那直接返回0
    for(int j=1;j<len2;j++){  //然后从下标为1开始逐个查找
        i=temp[i][b[j]-'a'];
        /*找到了上一个字符在a中的位置,然后利用temp数组
       找出在它后面的第一次出现的这个要查找的字符的位置,继续存入i中*/
        if(i==-1)  return 0; //没有则直接返回0
    }
    return 1;
}

总的代码如下:

#include<bits/stdc++.h>
using namespace std;
string a,b;
int temp[1000010][30];
int ans[30];
void deal(){
    memset(ans,-1,sizeof(ans));
    int len=a.length();
    for(int i=len-1;i>=0;i--){  //从后往前遍历每个位置 
        for(int k=0;k<26;k++){   
            temp[i][k]=ans[k];  //将该位置后面的出现的从a-z的第一个位置记录下来
        }
        ans[a[i]-'a']=i;   
    }
}
bool judge(){
    int len1=a.length(),len2=b.length();
    int i=ans[b[0]-'a'];  //首先要找到字符串b中的第一个字符在字符串a中的位置存入i
    if(i==-1)  return 0;
    for(int j=1;j<len2;j++){
        i=temp[i][b[j]-'a'];
        /*找到了上一个字符在a中的位置,然后利用temp数组
       找出在它后面的第一次出现的这个要查找的字符的位置,继续存入i中*/
        if(i==-1)  return 0;
    }
    return 1;
}
int main(){
    int n;
    cin>>a;
    deal();
    /*完成这个后,那么我们就将母串的每一个位置的后面
    第一次出现a,b,c...z的位置都记录在了temp数组里面*/ 
    cin>>n;
    while(n--){
        cin>>b;
        if(judge())  cout<<"Yes"<<endl;
        else  cout<<"No"<<endl;
    }
    return 0;
}

有错误请指出,谢谢!!!