首页 > > 程序设计 > C/C++ >

洛谷P3966 [TJOI2013]单词(AC自动机)

2018-07-03 01:01:15来源：博客园阅读 ()

题目描述

小张最近在忙毕设,所以一直在读论文。一篇论文是由许多单词组成但小张发现一个单词会在论文中出现很多次,他想知道每个单词分别在论文中出现了多少次。

输入输出格式

输入格式：

第一行一个整数N,表示有N个单词。接下来N行每行一个单词,每个单词都由小写字母(a-z)组成。(N≤200)

输出格式：

输出N个整数,第i行的数表示第i个单词在文章中出现了多少次。

输入输出样例

输入样例#1：复制

3
a
aa
aaa

输出样例#1：复制

6
3
1

说明

数据范围

30%的数据，单词总长度不超过10^3

100%的数据，单词总长度不超过10^6

自己xjb YY了一个做法居然1Ahhh

首先应该一眼就能看出是AC自动机。

那么我们先把所有串的AC自动机搞出来，然后记录下他们拼起来的串，用随便一个字符分隔

暴力枚举每一个串，把经过的路径上的权值$+1$，表示该位置代表的串又多出现了一次。

这样我们就统计出了与它一模一样的串的出现次数。

还有一种情况，即当它作为某些串的后缀出现。

此时，根据AC自动机的性质不难发现，我们要求的答案即为该节点在$fail$树上子树的和

然后直接暴力把$fail$树建出来，树形DP统计答案即可

就是跑的有点慢

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN = 1e6 + 100, B = 28;
int T;
char s[MAXN], a[MAXN];
int fail[MAXN], ch[MAXN][28], val[MAXN], tot = 0, root = 0;
void insert(char *s) {
    int N = strlen(s + 1);
    int now = root;
    for(int i = 1; i <= N; i++) {
        int x = s[i] - 'a';
        if(!ch[now][x]) ch[now][x] = ++tot;
        now = ch[now][x];
        val[now]++;
    }
}   
vector<int> v[MAXN];
void GetFail() {
    queue<int> q; 
    for(int i = 0; i < B; i++) if(ch[root][i]) q.push(ch[root][i]);
    while(!q.empty()) {
        int p = q.front(); q.pop();
        for(int i = 0; i < B; i++) {
            if(ch[p][i]) fail[ch[p][i]] = ch[fail[p]][i], q.push(ch[p][i]);
            else ch[p][i] = ch[fail[p]][i];
        }
        v[fail[p]].push_back(p);
    }
}
void GetVal(int x) {
    for(int i = 0; i < v[x].size(); i++)
        GetVal(v[x][i]), val[x] += val[v[x][i]];
}
void GetAns(char *s) {
    int N = strlen(s + 1), now = root, ans = 0;
    for(int i = 1; i <= N; i++) {
        int x = s[i] - 'a';
        if(x == 26) printf("%d\n", val[now]), now = root, ans = 0;
        now = ch[now][x];
    }
    printf("%d", val[now]);
}
int main() {
    //freopen("a.in", "r", stdin); 
    scanf("%d", &T);
    for(int i = 1; i <= T; i++) {
        scanf("%s", s + 1);
        insert(s);
        s[0] = 'z' + 1;
        strcat(a, s);
    }
    GetFail();
    GetVal(0);
    GetAns(a); 
    return 0;
}