M_sea

洛谷2336 [SCOI2012]喵星球上的点名
LuoguBZOJ分析强烈谴责$\mathrm{Luogu}$这种加超出原题范围的数据的行为...直接把我的 $\...
扫描右侧二维码阅读全文
02
2019/04

洛谷2336 [SCOI2012]喵星球上的点名

Luogu

BZOJ

分析

强烈谴责$\mathrm{Luogu}$这种加超出原题范围的数据的行为...直接把我的 $\mathrm{AC}$ 自动机卡 $\mathrm{TLE}$ 了...

如果想看跑得飞快的题解,请戳某位神仙的 $\mathrm{blog}$


把所有点名串插入到 $\mathrm{AC}$ 自动机里面,然后把所有的名字丢进去匹配即可。

怎么匹配?暴力跳 $\mathrm{fail}$ 啊...

然后要用 $\mathrm{map/unordered\_map}$ 存 $ch$ 。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}
inline void get(vector<int>& a) {
    int x=read(); a.resize(x+1),a[0]=x;
    for (re int i=1;i<=x;++i) a[i]=read();
}

const int N=100000+10;

int n,m;
vector<int> a[N],b[N],c[N];

unordered_map<int,int> ch[N];
int fail[N],ed[N];
set<int> eds[N];
int tot=0;

inline void insert(vector<int> s,int id) {
    int now=0,l=s[0];
    for (re int i=1;i<=l;++i) {
        int w=s[i];
        if (!ch[now][w]) ch[now][w]=++tot;
        now=ch[now][w];
    }
    eds[now].insert(id),ed[now]=1;
}


#define IT unordered_map<int,int>::iterator
inline void getfail() {
    queue<int> Q;
    for (IT it=ch[0].begin();it!=ch[0].end();++it)
        Q.push(it->second);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        for (IT it=ch[u].begin();it!=ch[u].end();++it) {
            int v=it->second,w=it->first,p=fail[u];
            while (p&&!ch[p][w]) p=fail[p];
            if (ch[p][w]) fail[v]=ch[p][w];
            Q.push(v),ed[v]|=ed[fail[v]];
        }
    }
}
#undef IT

int ans1[N],ans2[N],vis[N];

#define IT set<int>::iterator
inline void solve(vector<int> s,int id) {
    int now=0,l=s[0];
    for (re int i=1;i<=l;++i) {
        int w=s[i];
        if (ch[now][w]) now=ch[now][w];
        else {
            while (now&&!ch[now][w]) now=fail[now];
            if (ch[now][w]) now=ch[now][w];
        }
        if (ed[now]) {
            int p=now;
            while (p) {
                for (IT it=eds[p].begin();it!=eds[p].end();++it)
                    if (vis[*it]!=id) vis[*it]=id,++ans1[*it],++ans2[id];
                p=fail[p];
            }
        }
    }
}
#undef IT
    
int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) get(a[i]),get(b[i]);
    for (re int i=1;i<=m;++i) get(c[i]);
    
    for (re int i=1;i<=m;++i) insert(c[i],i);
    getfail();
    for (re int i=1;i<=n;++i) solve(a[i],i),solve(b[i],i);
    for (re int i=1;i<=m;++i) printf("%d\n",ans1[i]);
    for (re int i=1;i<=n;++i) printf("%d ",ans2[i]); puts("");
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 31 PM

发表评论