M_sea

洛谷3966 [TJOI2013]单词
LuoguBZOJ分析多个串,考虑$\texttt{AC自动机}$。首先还是建出$\texttt{AC自动机}$,...
扫描右侧二维码阅读全文
22
2019/01

洛谷3966 [TJOI2013]单词

Luogu

BZOJ

分析

多个串,考虑$\texttt{AC自动机}$。

首先还是建出$\texttt{AC自动机}$,考虑一下怎么处理。

将$\texttt{AC自动机}$上每个节点的权值设为这个节点属于多少个串,每个字符串出现的次数为它的$endpos$所在节点的子树的权值和。

所以建$\texttt{Trie}$树的时候顺便处理掉权值,然后按照反的拓扑序往上累加即可。

这个拓扑序怎么搞?$\texttt{getFail}$的时候队列里的序列就是啊。

如果还不懂,见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#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;
}

const int N=200+10;
const int L=1000000+10;

struct node {
    int ch[26],fail,size;
} t[1000000];
int cnt=0;
int endpos[N];

inline void insert(int id,char* s,int l) {
    int now=0;
    for (re int i=0;i<l;++i) {
        if (!t[now].ch[s[i]-'a']) t[now].ch[s[i]-'a']=++cnt;
        now=t[now].ch[s[i]-'a'],++t[now].size;
    }
    endpos[id]=now;
}

int Q[1000000];
int head=0,tail=-1;

inline void getFail() {
    Q[++tail]=0;
    while (head<=tail) {
        int u=Q[head++];
        for (re int i=0;i<26;++i) {
            if (t[u].ch[i]) {
                if (u) t[t[u].ch[i]].fail=t[t[u].fail].ch[i];
                Q[++tail]=t[u].ch[i];
            }
            else t[u].ch[i]=t[t[u].fail].ch[i];
        }
    }
}

char str[L];

int main() {
    int n; scanf("%d\n",&n);
    for (re int i=1;i<=n;++i) {
        scanf("%s",str);
        insert(i,str,strlen(str));
    }
    getFail();
    for (re int i=cnt;i>=0;--i) t[t[Q[i]].fail].size+=t[Q[i]].size;
    for (re int i=1;i<=n;++i) printf("%d\n",t[endpos[i]].size);
    return 0;
}
最后修改:2019 年 05 月 26 日 06 : 42 PM

发表评论