题解 | #正则匹配#

#include <iostream>
#include <vector>
using namespace std;

const int N=1e6;
vector<vector<int>> nodes;
vector<int> end_ids;
//vector<int> visited;
int id=0;
int q;
int n;

void buildDictionaryTree(string& s)
{
    int current_node_id=0;
    for(auto c:s)
    {
        int letter=c-'a';
        //current_node_id=0;
        //visited[current_node_id]++;
        if(nodes[current_node_id][letter]==0)
        {
            nodes[current_node_id][letter]=++id;
        }
        current_node_id=nodes[current_node_id][letter];
        
    }
    ++end_ids[current_node_id];
}

int dfs(int id)
{
    if(id==0)return 0;
    int sum=end_ids[id];
    for(int i=0;i<26;i++)
    {
        sum+=dfs(nodes[id][i]);
    }
    return sum;
}

int countStringPrefixQuantity(string& s)
{
    int current_node_id=0;
    for(int i=0;i<s.length();i++)
    {
        //current_node_id=0;
        int letter=(s[i]-'a');
        current_node_id=nodes[current_node_id][letter];
        if(current_node_id==0)
        {
            return 0;
        }
    }
    return dfs(current_node_id);
}

int main() {
    cin>>n;
    nodes=vector<vector<int>>(N,vector<int>(26,0));
    end_ids=vector<int>(N,0);
    //visited=vector<int>(10240,0);
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        buildDictionaryTree(s);
    }
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        string s;
        cin>>s;
        cout<<countStringPrefixQuantity(s)<<endl;
    }
}
// 64 位输出请用 printf("%lld")