Fork me on GitHub

[SCOI-2012] 喵星球上的点名 AC自动姬+map

发表于 | 分类于
字数统计: 664字 | 阅读时长 ≈ 4分钟

题面

BZOJ-2754

分析

直接暴力对每个串开个map建AC自动姬.

写起来其实不难的,思维难度也不是很高.主要的技巧在于常数的处理.

看上去空间爆炸但是居然过了!!

LUOGU好像加了一组恶心数据卡掉了这种辣鸡做法

好吧其实正解好像要用到主席树可惜我还不会.

菜啊 qwq

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+4;
#define RG register
inline int read(void)
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,ans1[maxn],ans2[maxn];
vector<int>a[maxn<<1],status[maxn],V,M;
bool vis[maxn],mk[maxn];
map<int,int>to[maxn];
map<int,int>::iterator it;
struct Aho_Corasick
{
    int cnt,ans;
    int fail[maxn],q[maxn];
    Aho_Corasick()
    {
        cnt = 1;
        for (RG int i = -1; i <= 1e4; i++)
            to[0][i] = 1;
        fail[1] = 0;
    }
    void Insert(int id)
    {
        int L = read(),nn = 1;
        for (RG int i = 1; i <= L; i++)
        {
            int x = read();
            if (!to[nn][x]) to[nn][x]=++cnt;
            nn = to[nn][x];
        }
        status[nn].push_back(id);
    }
    void build_fail()
    {
        queue<int>q;
        q.push(1);
        while(!q.empty())
        {
            int tmp = q.front();
            q.pop();
            for (it = to[tmp].begin(); it != to[tmp].end(); it++)
            {
                int t1 = it->first,t2 = it->second;
                int k = fail[tmp];
                //printf("%d %d %d\n",t1,t2,k);
                while(!to[k][t1]) k = fail[k];
                fail[t2] = to[k][t1];
                q.push(t2);
            }
        }
    }
    void get(int id,int x)
    {
        for (RG int i = x; i != 0; i = fail[i])
            if (!vis[i])
            {
                vis[i]  = 1;
                V.push_back(i);
                for (RG int j = 0; j < status[i].size(); j++)
                {
                    if (!mk[status[i][j]])
                    {
                        mk[status[i][j]] = 1;
                        M.push_back(status[i][j]);
                        ans1[status[i][j]] ++;
                        ans2[id]++;
                    }
                }
            }
            else break;
    }
    void sett(void)
    {
        for (RG int i = 0; i < V.size(); i++) vis[V[i]] = 0;
        for (RG int i = 0; i < M.size(); i++) mk[M[i]] = 0;
        V.clear(); M.clear();
    }
    void solve(int x)
    {
        int  nn = 1;
        for (RG int i = 0; i < a[x].size(); i++)
        {
            int t = a[x][i];
            while(!to[nn][t]) nn = fail[nn];
            nn = to[nn][t];
            get(x,nn);
        }
        sett();
    }
}AC;
int main(int argc, char *argv[])
{
    n = read(); m = read();
    int L,x;
    for(RG int i=1;i<=n;i++)
    {
        L=read();
        while(L--)x=read(),a[i].push_back(x);
        a[i].push_back(-1);
        L=read();
        while(L--)x=read(),a[i].push_back(x);
    }
    for(RG int i=1;i<=m;i++) AC.Insert(i);
    AC.build_fail ();
    for(RG int i=1;i<=n;i++)
        AC.solve(i);
    for(RG int i=1;i<=m;i++)printf("%d\n",ans1[i]);
    for(RG int i=1;i<=n;i++)
    {
        printf("%d",ans2[i]);
        if (i != n) putchar(' '); 
    }
    return 0;
}