P10470 前缀统计

点击查看代码

#include<bits/stdc++.h>using namespace std;const int N=1e6;
int n,m,idx;
int cnt[N];
char str[N];
int son[N][26];void insert(char* str)
{int p=0;for(int i=0;str[i];i++){int u=str[i]-'a';if(!son[p][u]) son[p][u]=++idx;p=son[p][u];}cnt[p]++;
}void query(char* str)
{int p=0;int ans=0;for(int i=0;str[i];i++){int u=str[i]-'a';if(!son[p][u]) break;p=son[p][u];ans+=cnt[p];}cout<<ans<<endl;
}int main()
{cin>>n>>m;while(n--){cin>>str;insert(str);}while(m--){cin>>str;query(str);}return 0;
}

依旧是简单的trie树模板，做出标记后查找即可，本题还深化了一点就是第一个p并不代表任何节点，也就是p=son【p】【u】才算是起点，可以把每次p=son【p】【u】看作是一个新节点，然后对这个节点进行操作即可