【每日一题】4月2日 月月查华华的手机

问题本质：判断一个序列是不是另一个序列的子序列。

基本解法：定义两个指针i、j分别指向s串和t串，遍历s串如果，则j++。这样的做法最坏的情况会遍历整个s串，虽然对于单次查询复杂度可以接受，但对于本题的多次查询显然不行。

贪心：如果在s串中有多个，那么肯定选用i值小的，因为i值小的可拓展性更好，或者说i值小的无法找到串t，则i值大的也无法找到。

问题关键：假设已经找到，如何快速的找到？

预处理：从后往前遍历串s，并用数组记住每个字符最早出现的位置，并把的值赋给，这样找到时可以直接跳到。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 2e5 + 117;

int n;
int to[MAXN][30], first[30];
char s[MAXN], t[MAXN];
bool solve() {
    int len = strlen(t);
    int id = first[t[0] - 'a'];
    if(id == -1) return false;
    for(int i = 1; i < len; i++) {
        id = to[id][t[i] - 'a'];
        if(id == -1) return false;
    }
    return true;
}
int main() {
    scanf("%s", s);
    scanf("%d", &n);
    memset(first, -1, sizeof(first));
    for(int i = strlen(s) - 1; i >= 0; i--) {
        for(int j = 0; j < 30; j++) to[i][j] = first[j];
        first[s[i] - 'a'] = i;
    }
    while(n--) {
        scanf("%s", t);
        if(solve()) puts("Yes");
        else puts("No");
    }
    return 0;
}