字典树-前缀统计

佚名 6年前 (2019-04-07) 随笔 1265人围观抢沙发百度已收录

给定N个字符串S1,S2...SN,接下来m组询问，每次询问给一个字符串T，求S1~SN中有多少是T的前缀，输入的字符串总长度不超过10⁶

#include<bits/stdc++.h>
using namespace std; const int maxn=1e6+6; int trie[maxn][27]; // 创建一个节点大小为maxn 每个节点有27个方向的的字典树 
int tot=1;// 表示从1开始 
string s;   // 
void add() { int p=1; for(int i=0; i<s.size(); i++) { int k=s[i]-'a'+1; if(trie[p][k]==0) trie[p][k]=++tot; // 如果trie的节点为p时，而p的方向没有这个字母，则建立一个新的节点 
        p=trie[p][k]; // p存了这个节点的id 
 } ++trie[p][0]; } void get() { int ans=0,p=1; for(int i=0; i<s.size(); i++) { int k=s[i]-'a'+1; p=trie[p][k]; ans+=trie[p][0]; } cout<<ans<<endl; } int main() { memset(trie, 0, sizeof(trie)); int n, m; cin >> n >> m; while (n--) { cin>>s; add(); } while (m--) { cin>>s; get(); } return 0; }