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

对所有需要查询的字符串建立字典树，通过对字符串A的扫描在字典树上做遍历，确定所有可以到达的字典树节点从而确定答案。
扫描方法为先初始化只需要一个字母就能到达的节点（即字典树的根的所有子节点），然后对每一个字母找到所有可以到达的节点，再更新差一步到达的节点。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int p = 1000000007;

struct Node {
    vector<int> id;// 可能有相同的待查询字符串
    Node* c[26];
    Node() {
        for (int i = 0; i < 26; ++i)
            c[i] = NULL;
    }
};

Node* root = new Node;

char a[1001000], b[1001000];

vector<Node*> v[26];
bool ans[1001000];

void solve() {
    for (int i = 0; i < 26; ++i)
        if (root->c[i] != NULL)
            v[i].push_back(root->c[i]);// 初始化差一个字母就能到达的位置
    int len = strlen(a);
    for (int i = 0; i < len; ++i)
        if (v[a[i] - 'a'].empty() == false) {
            vector<Node*> tmp = v[a[i] - 'a'];
            v[a[i] - 'a'].clear();
            for (int j = 0; j < tmp.size(); ++j) {// 已经到达的位置
                for (auto k = tmp[j]->id.begin(); k < tmp[j]->id.end(); ++k) {
                    ans[*k] = true;
                }
                for (int k = 0; k < 26; ++k)// 添加差一个字母就能到达的位置
                    if (tmp[j]->c[k] != NULL)
                        v[k].push_back(tmp[j]->c[k]);
            }
        }
}

int n;

int main() {
    scanf("%s", a);
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%s", b);
        int len = strlen(b);
        Node* r = root;// 建字典树
        for (int j = 0; j < len; ++j) {
            if (r->c[b[j] - 'a'] == NULL)
                r->c[b[j] - 'a'] = new Node;
            r = r->c[b[j] - 'a'];
        }
        r->id.push_back(i);
    }
    solve();
    for (int i = 0; i < n; ++i)
        if (ans[i])
            printf("Yes\n");
        else
            printf("No\n");
    return 0;
}