C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define _rep(i, x, y) for(int i = x; i < y; ++i)
#define _dep(i,x,y) for(int i = x; i > y; i--)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PDD pair<db,db>
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define sf scanf
#define pf printf
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef vector<ll> VLL;
typedef vector<int> VI;
const ll mod = 1e9 + 7;
const int KINF = 0x3f3f3f3f;
class Trie{
public:
    Trie():_root(new TreeNode()){}
    /*把一个字符串插入前缀树*/ 
    void insert(const string& word){
        TreeNode* cur = _root.get();
        for(const char& c:word){
            if(!cur->child[c - 'a'])
                cur->child[c - 'a']=new TreeNode();
            cur=cur->child[c - 'a']; 
        }
        cur->end_cnt ++ ;//以该字符结尾的字符串数量
    }
    int search(const string& s) const{
        int ans = 0;
        const TreeNode* p = _root.get();
        for(const char& ch : s){
            p = p->child[ch - 'a'];
            if(!p) break;
            ans += p->end_cnt;

        }
        return ans;
    }
private:
    struct TreeNode{    
        TreeNode():end_cnt(0),child(26,nullptr){}
        ~TreeNode(){
            for(TreeNode* c:child) if(c) delete c;
        }
        int end_cnt;
        vector<TreeNode*> child;
    };
    unique_ptr<TreeNode> _root; //一个智能指针，这样不需要自己手动回收内存 
};
int main(){
    int n, m;
    cin >> n >> m;
    Trie tree;
    string T;
    _rep(i, 0, n){
        cin >> T;
        tree.insert(T);
    }
    while(m--){
        cin >> T;
        int ans = tree.search(T);
        cout << ans << endl;
    }
    return 0;
}