NC14612. string
描述
Bob has a dictionary with N words in it. There are M operators. Each operator is one of two kinds.
1. Add a string to the dictionary. It is guaranteed that the string s was not added before.
2. For the given string s find the number of occurrences of the strings from the dictionary. If some string p from the dictionary has several occurrences in s you should count all of them.
输入描述
The first line of the input gives the number of test cases T(T<=10); T test cases follow.
Each test case contains two integer N( 1≤N≤10^5) and M(1≤M≤10^5), The number of words in the dictionary initially, and the number of operators.
Next N line, each line has a string Wi, represents the ith word in the dictionary (0<|Wi|≤100000)
Next M line, each line contains integer t (1≤t≤2) and nonempty string s—the kind of the operator and the string to process. All strings consist of only lowercase English letters.
The sum of lengths of all strings in the input will not exceed 3*10^6.
For each operator of the second kind print the only integer c—the desired number of occurrences in the string s.
输出描述
For each operator of the second kind print the only integer c—the desired number of occurrences in the string s.
示例1
输入:
2 1 3 abc 2 abcabc 1 aba 2 abababc 2 6 abc bcd 2 abcd 2 bcd 1 abcd 2 abcd 2 abc 2 bcd
输出:
2 3 2 1 3 1 1
C++(g++ 7.5.0) 解法, 执行用时: 736ms, 内存消耗: 22816K, 提交时间: 2022-08-05 21:24:40
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,a,b) for(int i=a;i>=b;i--)
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int N=1e6+2,M=1e5+2;
int t[N][26],cnt,num[N],fail[N],last[N];
int id[M<<1];
void insert(string s,int p=0){
int x=0;
for(auto& i:s){
int k=i-'a';
if(!t[x][k])t[x][k]=++cnt;
x=t[x][k];
}
num[x]++;id[p]=x;
}
void build(){
queue<int>q;
rep(i,0,25)if(t[0][i])q.push(t[0][i]);
while(!q.empty()){
int k=q.front();q.pop();
rep(i,0,25){
int & son=t[k][i];
if(son)q.push(son),fail[son]=t[fail[k]][i];
else son=t[fail[k]][i];
last[son]=num[fail[son]]?fail[son]:last[fail[son]];
}
}
}
void reset(){
rep(i,1,cnt)num[i]=fail[i]=last[i]=0;
rep(i,0,cnt)rep(j,0,25)t[i][j]=0;cnt=0;
}
int query(string s){
int ans=0,x=0;
for(auto& i:s){
int k=i-'a';x=t[x][k];
for(int j=x;j;j=last[j])ans+=num[j];
}
return ans;
}
void solve(){
reset();
int n,m;cin>>n>>m;
rep(i,1,n){
string s;cin>>s;insert(s);
}
vector<int>cmd(m+1);vector<string> s(m+1);
rep(i,1,m){
cin>>cmd[i]>>s[i];
if(cmd[i]==1)insert(s[i],i);
}
build();
vector<int> ans(m+1);
rev(i,m,1){
if(cmd[i]==1)num[id[i]]--;
else ans[i]=query(s[i]);
}
rep(i,1,m)if(cmd[i]==2)cout<<ans[i]<<endl;
}
int main(){
fastio;
int t;cin>>t;
while(t--)solve();
//system("pause");
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 753ms, 内存消耗: 27240K, 提交时间: 2020-03-24 13:57:31
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+100;
string s[N];
int op[N];
struct AC
{
int t[N][26],tot=0,F[N],ed[N];
void init()
{
for(int i=0;i<=tot;i++)
{
memset(t[i],0,sizeof t[i]);
F[i]=ed[i]=0;
}
tot=0;
}
void insert(string &s)
{
int p=0;
for(int i=0;s[i];i++)
{
int c=s[i]-'a';
if(t[p][c]==0) t[p][c]=++tot;
p=t[p][c];
}
ed[p]++;
}
void build()
{
queue<int>q;
for(int i=0;i<26;i++) if(t[0][i])q.push(t[0][i]);
while(q.size())
{
int tmp=q.front();
q.pop() ;
ed[tmp]+=ed[F[tmp]];
for(int i=0;i<26;i++)
{
if(t[tmp][i])
{
F[t[tmp][i]]=t[F[tmp]][i];
q.push(t[tmp][i]);
}
else t[tmp][i]=t[F[tmp]][i];
}
}
}
int query(string &s)
{
int ans=0,p=0;
for(int i=0;s[i];i++)
{
int c=s[i]-'a';
p=t[p][c];
ans+=ed[p];
}
return ans;
}
}AC;
int ans[N];
void solve(int l,int r)
{
if(l==r) return ;
int mid=l+r>>1;
solve(l,mid);
solve(mid+1,r);
AC.init();
for(int i=l;i<=mid;i++) if(op[i]==1) AC.insert(s[i]);
AC.build();
for(int i=mid+1;i<=r;i++) if(op[i]==2) ans[i]+=AC.query(s[i]);
}
int main()
{
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
AC.init();
for(int i=1;i<=n;i++)
{
cin>>s[i];
op[i]=1;
ans[i]=0;
}
for(int i=1;i<=m;i++)cin>>op[i+n]>>s[i+n],ans[i+n]=0;
solve(1,n+m);
for(int i=1;i<=m;i++) if(op[i+n]==2) cout<<ans[i+n]<<"\n";
}
return 0;
}