月月查华华的手机

思路

以为是一个很简单的双指针

但是第一次写完就超时了

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int inf = INT_MAX;
typedef pair<int, int> pii;
typedef priority_queue<int, vector<int>, greater<int>> small_heap;
#define int long long
int n;
string s;
bool isSeq(string &p)
{
    int m = p.length();
    int j =  0 ;
    for (int i = 0 ; i < n; i++)
    {
        if (s[i] == p[j]) j++;
    }
    return j == m ; 
}
int32_t main()
{
    cin >> s;
    int t;
    cin >> t;
    n = s.length();
    while (t--)
    {
        string p;
        cin >> p;
        cout << (isSeq(p) ? "Yes" : "No") << endl;
    }
    return 0;
}

然后想了下, 不应该枚举大串的, 大串预处理好
枚举小串就行了

大串的预处理:
ne[i][ch] : 表示 第 i 个字母后, 第一个 ch 的位置

    vector<vector<int>> ne(n + 1, vector<int>(26, 0));

    for (int i = n - 1; 0 <= i; i--)
    {
        for (int c = 0; c < 26; c++)
        {
            ne[i][c] = ne[i + 1][c];
        }
        ne[i][s[i + 1] - 'a'] = i + 1;
    }

小串只需要枚举链表, 看看能不能到结尾就好
开始 : ne[0][ch] ;
前进 : k = ne[k][ch];
枚举到最后, 不是 0 就行

    auto get = [&]()
    {
        int m = strlen(s + 1);
        int k = 0;
        for (int i = 1; i <= m; i++)
        {
            if (ne[k][s[i] - 'a'])
                k = ne[k][s[i] - 'a'];
            else
                return 0;
        }
        return 1;
    };

ac 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int inf = INT_MAX;
typedef pair<int, int> pii;
typedef priority_queue<int, vector<int>, greater<int>> small_heap;
#define int long long
int n, t;
char s[N];
int32_t main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1);

    vector<vector<int>> ne(n + 1, vector<int>(26, 0));

    for (int i = n - 1; 0 <= i; i--)
    {
        for (int c = 0; c < 26; c++)
        {
            ne[i][c] = ne[i + 1][c];
        }
        ne[i][s[i + 1] - 'a'] = i + 1;
    }

    auto get = [&]()
    {
        int m = strlen(s + 1);
        int k = 0;
        for (int i = 1; i <= m; i++)
        {
            if (ne[k][s[i] - 'a'])
                k = ne[k][s[i] - 'a'];
            else
                return 0;
        }
        return 1;
    };

    cin >> t;
    while (t--)
    {
        scanf("%s", s + 1);
        cout << (get() ? "Yes" : "No") << endl;
    }
    return 0;
}