题目:
题目大意:给出一个字符串,我们假设它为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; }
有错误请指出,谢谢!!!