题解 | 字符串匹配（字典树）

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define wkr ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N = 1e5 + 10;
int cnt[N],a[N][128],tot;
int find(string t){
    int p = 0;
    for(int i = 0;i<(int)t.size();i++){
        if(t[i] >= 'A' && t[i] <= 'Z'){
            t[i] = char(t[i] - 'A' + 'a');
        }
        if(a[p][(int)t[i]]) p = a[p][(int)t[i]];
        else return 0;
    }
    return cnt[p];
}
void solved(){
    int n; cin >> n;
    vector<string>s(n + 1);
    for(int i = 1;i<=n;i++) cin >> s[i];
    int p = 0;
    string t; cin >> t;
    for(int i = 0;i<(int)t.size();i++){
        vector<char>nex;
        if(t[i] == '['){
            ++i;
            while(i < (int)t.size() && t[i] != ']'){
                if(t[i] >= 'A' && t[i] <= 'Z'){
                    t[i] = char(t[i] - 'A' + 'a');
                }
                nex.push_back(t[i]);
                ++i;
            }
        }
        else{
            if(t[i] >= 'A' && t[i] <= 'Z'){
                t[i] = char(t[i] - 'A' + 'a');
            }
            nex.push_back(t[i]);
        }
        sort(nex.begin(),nex.end());
        nex.erase(unique(nex.begin(),nex.end()),nex.end());
        int pp = ++tot;
        for(auto ne:nex){
            a[p][(int)ne] = pp;
        }
        p = pp;
    }
    cnt[p] = 1;
    for(int i = 1;i<=n;i++){
        if(find(s[i])){
            cout << i <<" "<<s[i]<<endl;
        }
    }
}
signed main(){
    wkr;
    int T = 1; //cin >> T;
    while(T--){
        solved();
    }
}