由于本蒟蒻刚学算法,所以用了个基础的做法,跑了138ms,内存1892K
之后学习了题解中的方法,内存比第一种方法大十倍,但运行时间短了一点,(数据少的原因吧）
收获颇丰,orz
题意
给定字符串s1,有n次查询,每次查询给出一个字符串s2,问s2是否是s1的子序列。
思路
把s2中的字母按顺序在s1中查询,找到一个后则往后接着找,看能否都找到。
代码
1、暴力

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n;
char s1[maxn],s2[maxn];
int main(){
    scanf("%s",s1);
    int len1=strlen(s1);//计算s1的长度
    scanf("%d",&n);
    while(n--){
        scanf("%s",s2);
        int j=0;
        int len2=strlen(s2);//计算s2的长度
        for(int i=0;i<len1;i++){
            if(j==len2) break;//s2中的字母全部在s1中找到,结束循环
            else if(s1[i]==s2[j]) ++j;//找到一个字母,然后去找下一个
        }
        if(j==len2) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

2、枚举优化（刚学了题解中的方法，毕竟我太菜）

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,last[30],nex[maxn][30];
char s1[maxn],s2[maxn]; 
void solve1(){
    int len1=strlen(s1);
    memset(last,-1,sizeof(last));//-1表示不存在
    for(int i=len1-1;i>=0;i--){
        for(int j=0;j<26;j++) nex[i][j]=last[j];//将last['a'...'z']复制给当前的next[i]['a'...'z']
        last[s1[i]-'a']=i;//当前字母修改last
    }
}
bool solve2(){
    int len1=strlen(s1),len2=strlen(s2);
    int i=last[s2[0]-'a'];//i初值直接赋为A中子串首字母的位置
    if(i==-1) return 0;//如果A中没有这个首字母 直接无解
    for(int j=1;j<len2;j++){//j遍历子串中的字母（首字母就不必了）
        i=nex[i][s2[j]-'a'];//i跳到前一个字母后面的当前字母
        if(i==-1) return 0;
    }
    return 1;
}
int main(){
    scanf("%s",s1);
    solve1();
    scanf("%d",&n);
    while(n--){
        scanf("%s",s2);
        if(solve2()) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}