90pts求调
查看原帖
90pts求调
1277550
cx2021hjxhjx楼主2024/7/10 11:10

rt

#include<bits/stdc++.h>
#define N 100010
using namespace std;
map<int,int>trie[N];
vector<int>a[20001],st[N],USE,MARK;
int f[N],len,tot=1,n,m,call[50001],mi[20001],x;
queue<int>q;
bool mark[N],use[50001];
struct ac{
    void insert(int i){
        int x,root=1;
        while(len--){
            cin>>x;
            if(!trie[root][x]) trie[root][x]=++tot;
            root=trie[root][x];
        }
        st[root].push_back(i);
    }
    void fail(){
        q.push(1);
		int j;
        while(q.size()) {
            int now=q.front();
			q.pop();
            for(auto it=trie[now].begin();it!=trie[now].end();it++){
                int w=it->second,e=it->first;
                q.push(w);
                j=f[now];
                while(!trie[j][e]) j=f[j];
                f[w]=trie[j][e];
            } 
        }
    }
    void get(int now,int who){
        for(int i=now;i;i=f[i]){
            if(mark[i]) return;
            else{
                mark[i]=1;
                MARK.push_back(i);
                for(int j=0;j<st[i].size();j++){
                    if(!use[st[i][j]]){
                        use[st[i][j]]=1;
                        USE.push_back(st[i][j]);
                        mi[who]++;
                        call[st[i][j]]++;
                    }
                }
            }
        }
    }
    void sol(int k){
        int id,root=1;
        for(int i=0;i<a[k].size();i++){
            id=a[k][i];
            while(!trie[root][id]) root=f[root];
            root=trie[root][id];
            get(root,k);
        }
        for(int i=0;i<MARK.size();i++) mark[MARK[i]]=0;
        for(int i=0;i<USE.size();i++) use[USE[i]]=0;
        MARK.clear();
		USE.clear();
    }
}tree;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>len;
        while(len--){
            cin>>x;
            a[i].push_back(x);
        }
        a[i].push_back(-1);
        cin>>len;
        while(len--){
            cin>>x;
            a[i].push_back(x);
        }
    }
    for(int i=1;i<=m;i++){
        cin>>len;
        tree.insert(i);
    }
    for(int i=-1;i<=10000;i++) trie[0][i]=1;
    tree.fail();
    for(int i=1;i<=n;i++)    
    tree.sol(i);
    for(int i=1;i<=m;i++) cout<<call[i]<<'\n';
    for(int i=1;i<=n;i++) cout<<mi[i]<<" ";
    return 0;
}
2024/7/10 11:10
加载中...