P3966 [TJOI2013]单词

P3966 [TJOI2013]单词

题意

给出一堆的单词，求出每个单词在这堆单词里面出现的次数。

思路

建立一颗树，首先找出每个出现的次数，然后从最小面开始进行遍历，从而进行累加，就可以直接求出每一个的个数。
比如：ab，abbcab，这里ab在第二个里面出现了两次，首先就可以直接求出次数。后面的ab是可以直接走向最前面的ab的。
因为他们两是一样的，所以他就可以求出每一个的数量

代码

//想按照特定的方式进行遍历，可以走图
#include <bits/stdc++.h>
using namespace std;
const int N=205,M=1e6+5;

int ch[M][26],flag[M],fail[M],cnt[M],tot=0;
void insert(int id,string s) {
    int p=0,n=s.length();
    for(int i=0;i<n;i++) {
        int v=s[i]-'a';
        if(ch[p][v]==0)ch[p][v]=++tot;
        p=ch[p][v];
        cnt[p]++;
    }
    flag[id]=p;
}

int h[M],ne[M<<1],e[M<<1],sum;
void add(int from,int to) {
    e[++sum]=to;  ne[sum]=h[from];  h[from]=sum;
}

void build() {
    queue<int>q;
    for(int i=0;i<26;i++)
        if(ch[0][i])q.push(ch[0][i]);
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        for(int i=0;i<26;i++) {
            if(ch[now][i]) {
                fail[ch[now][i]]=ch[fail[now]][i];
                q.push(ch[now][i]);
            }
            else ch[now][i]=ch[fail[now]][i];
        }
    }
    for(int i=1;i<=tot;i++)
        add(fail[i],i);
}

int in[M],ans[M];
void dfs(int now) {
    for(int i=h[now];i;i=ne[i]) {
        int to=e[i];
        dfs(to);
        cnt[now]+=cnt[to];
    }
}

string s[N];
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>s[i];
        insert(i,s[i]);
    }
    build();
    for(int i=1;i<=tot;i++)cout<<fail[i]<<' ';
    dfs(0);
    for(int i=1;i<=n;i++)cout<<cnt[flag[i]]<<'\n';
    return 0;
}