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

京公网安备 11010502036488号