屏蔽网站推广,wordpress申请子站,wordpress forget主题,县区社保经办网站建设【传送门#xff1a;BZOJ3172】 简要题意#xff1a; 给出n个单词#xff0c;你可以理解为将这些单词变成一个个段落#xff0c;然后求出每个单词在所有段落中出现的次数 题解#xff08;一#xff09;#xff1a; 刚开始不是很懂题目#xff0c;结果发现将所有单词看成…【传送门BZOJ3172】 简要题意 给出n个单词你可以理解为将这些单词变成一个个段落然后求出每个单词在所有段落中出现的次数 题解一 刚开始不是很懂题目结果发现将所有单词看成一篇文章每个单词看成一个段落就懂了 由于某种unbelievable的原因我刚好做了AC自动机的专题训练看到这道题就秒想AC自动机 将每个单词放进AC自动机里每个点的s表示有多少个单词经过然后在构建失败指针的时候通过队列来更新s值怎么更新呢假设有一个i点它的失败指针指向j设sj为从根到j点所构成的字符串si为从根到i点所构成的字符串那么我们可以知道sj为si的后缀也说明了si中有sj的出现那么就将j点的s值加上i点的s值达到更新且不重复的目的来求出答案 参考代码一 #includequeue
#includecstdio
#includecstring
#includealgorithm
#includecstdlib
#includecmath
using namespace std;
struct node
{int s,c[27],fail;node(){sfail0;memset(c,-1,sizeof(c));}
}t[1100000];
int tot,ans,n;
char a[1100000];
int ed[210];
void bt(int k,int root)
{int xroot,lenstrlen(a1);for(int i1;ilen;i){int ya[i]-a1;if(t[x].c[y]-1){t[x].c[y]tot;}xt[x].c[y];t[x].s;}ed[k]x;
}
int list[1100000];
void bfs()
{int x;int head1,tail1;list[1]0;while(headtail){xlist[head];for(int i1;i26;i){int sont[x].c[i];if(son-1)continue;if(x0) t[son].fail0;else{int jt[x].fail;while(j!0t[j].c[i]-1) jt[j].fail;t[son].failmax(t[j].c[i],0);int xt[son].fail,yson;}list[tail]son;}head;}for(int itail;i1;i--) t[t[list[i]].fail].st[list[i]].s;
}
int main()
{anstot0;scanf(%d,n);for(int i1;in;i){scanf(%s,a1);bt(i,0);}bfs();for(int i1;in;i){printf(%d\n,t[ed[i]].s);}return 0;
} 题解二 A了这道题之后才发现早在之前就A了心酸 那我们就来搞一下第二种想法 很容易就想到AC自动机但是单单是AC自动机还不行 这时就要用AC自动机的延伸——fail树来做时常膜一膜算法有益身体健康 fail树这个玩意就是将AC自动机中fail指针当成是一条边然后建成一棵树 由于trie树上的每个点相当于一个字符串所以这棵fail树父亲节点是儿子节点所构成字符串的最长后缀 这样子对于这道题而言fail树简直就是神一般的存在QAQ 首先将每个字符串放进trie树里面并且每经过一个trie树里的点就用s数组记录这个字符串出现的个数每经过一次就加一然后构造AC自动机然后在构造AC自动机的过程中对每个点的fail指针进行建边然后用dfs从根往下遍历把s数组从下往上累加 然后在输入每个字符串的时候记录每个字符串的最后一个字符在trie树上的编号然后一个一个输出s[end[i]]end[i]表示第i个字符串最后一个字母在trie树上的编号 参考代码二 #includequeue
#includecstdio
#includecstring
#includealgorithm
#includecstdlib
#includecmath
using namespace std;
struct node
{int c[27],fail;node(){fail0;memset(c,-1,sizeof(c));}
}t[1100000];
int tot,n;
char st[1100000];
int s[1100000];
int end[1100000];
void bt(int root,int z)
{int xroot,lenstrlen(st1);for(int i1;ilen;i){int yst[i]-a1;if(t[x].c[y]-1){t[x].c[y]tot;}xt[x].c[y];s[x];}end[z]x;
}
struct edge
{int x,y,next;
}a[1100000];int len,last[1100000];
void ins(int x,int y)
{len;a[len].xx;a[len].yy;a[len].nextlast[x];last[x]len;
}
queueint q;
void bfs()
{int x;q.push(0);while(q.empty()0){xq.front();for(int i1;i26;i){int sont[x].c[i];if(son-1)continue;if(x0) t[son].fail0;else{int jt[x].fail;while(j!0t[j].c[i]-1) jt[j].fail;t[son].failmax(t[j].c[i],0);}ins(t[son].fail,son);q.push(son);}q.pop();}
}
void dfs(int x)
{for(int klast[x];k;ka[k].next){int ya[k].y;dfs(y);s[x]s[y];}
}
int main()
{tot0;scanf(%d,n);for(int i1;in;i){scanf(%s,st1);bt(0,i);}len0;memset(last,0,sizeof(last));bfs();dfs(0);for(int i1;in;i) printf(%d\n,s[end[i]]);return 0;
} 转载于:https://www.cnblogs.com/Never-mind/p/7628734.html
