danihao123's Blog

首先……出题人语文不太好……估计和我这种语文很差的人还有差距……

这个提的意思是，给你若干个单词，输出每个单词在所有单词（而不是把所有单词连起来）中出现的次数。

然后肯定要AC自动机上失配函数搞一波辣……把BFS序倒过来搜，传递出现次数即可。还有这个题的数据范围好像也比给出的小很多……

代码：

/**************************************************************
    Problem: 3172
    User: danihao123
    Language: C++
    Result: Accepted
    Time:232 ms
    Memory:115080 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
const int maxn=205;
const int maxnode=1*1e6+5;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
int cnt[maxnode];
 
namespace ACAutomate{
    // Trie
    const int sigma_size=26;
    int Tree[maxnode][sigma_size];
    int siz;
    inline int idx(char c){
        return c-'a';
    }
    void InitAC(){
        siz=0;
        CL_ARR(Tree[0],0);
    }
    int Insert(char *s){
        register int i,n=strlen(s);
        register int u=0,c;
        REP(i,n){
            c=idx(s[i]);
            if(!Tree[u][c]){
                siz++;
                Tree[u][c]=siz;
                CL_ARR(Tree[siz],0);
            }
            u=Tree[u][c];
            cnt[u]++;
        }
        return u;
    }
    // AC Automate
    int f[maxnode];
    int Q[maxnode];
    void InitFail(){
        register int i,u,x,v,head=0,tail=0;
        f[0]=0;
        REP(i,sigma_size){
            u=Tree[0][i];
            if(u){
                f[u]=0;
                Q[tail++]=u;
            }
        }
        while(head<tail){
            u=Q[head];
            head++;
            REP(i,sigma_size){
                x=Tree[u][i];
                if(!x){
                    continue;
                }
                Q[tail++]=x;
                v=f[u];
                while(v && !Tree[v][i])
                    v=f[v];
                f[x]=Tree[v][i];
            }
        }
        for(i=tail-1;i>=0;i--)
            cnt[f[Q[i]]]+=cnt[Q[i]];
    }
};
 
char buf[maxnode];
int pos[maxn];
int main(){
    int n;
    register int i;
    scanf("%d",&n);
    ACAutomate::InitAC();
    REP_B(i,n){
        scanf("%s",buf);
        pos[i]=ACAutomate::Insert(buf);
    }
    ACAutomate::InitFail();
    REP_B(i,n){
        printf("%d\n",cnt[pos[i]]);
    }
    return 0;
}