[BZOJ 3172]单词
转载请注明出处:http://danihao123.is-programmer.com/
首先……出题人语文不太好……估计和我这种语文很差的人还有差距……
这个提的意思是,给你若干个单词,输出每个单词在所有单词(而不是把所有单词连起来)中出现的次数。
然后肯定要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; }