题目：https://ac.nowcoder.com/acm/problem/23053

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

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

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

问题关键：假设已经找到$s[i]=t[j]$，如何快速的找到$s[k]=t[j+1],i<k$？

预处理：从后往前遍历串s，并用数组$first[]$记住每个字符最早出现的位置，并把$first[]$的值赋给$to[i][]$，这样找到$s[i]=t[j]$时可以直接跳到$s[k]=t[j+1],k=to[i][t[j+1]]$。这个预处理是优化的核心部分，如果不能理解的话建议造几个简单的样例手动推一下。

#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;
}

版权属于：小影

本文链接：http://kindkidll.com/index.php/archives/130/

所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。 您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。