Luogu

BZOJ

分析

注意到 fail 树中某个节点的子树中的节点都以该节点作为一个后缀。

因此对于每个单词,把 trie 上它到根路径上的所有点权值加 $1$ ,然后统计 fail 树中权值和就好了。

代码

//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 年 10 月 10 日 08 : 58 PM