360元网站建设,邯郸服务,中国建设教育网官网是什么网站,如何一个空间放两个网站引入 我们首先提出一个问题#xff1a; 给出n个串每个串的长度≤m 然后给出一个长度为k的串#xff0c;询问前n个串中有多少个是匹配成了的 暴力搜索 这题不是sb题目吗#xff1f; 随随便便O(kmn)跑过。 。。。。 n10000 m50 k1000000 。。。。 好吧——我们用AC自动… 引入 我们首先提出一个问题 给出n个串每个串的长度≤m 然后给出一个长度为k的串询问前n个串中有多少个是匹配成了的 暴力搜索 这题不是sb题目吗 随随便便O(kmn)跑过。 。。。。 n10000 m50 k1000000 。。。。 好吧——我们用AC自动机吧 样例 首先我们举一个例子我们有n3个串he 和 her 和 she 然后我们通过构建Trie可以得到下图 这里红色的节点到根的路径可以构成一个串怎么那么像后缀自动机然后我们可以发现 正文 概念 我们使用Fail(i)表示i节点用虚线连接的边这样的边我们的作用就是当前节点到根的路径构成的字符串的最长的存在的后缀的串的位置。比如she 和 he 中 he 就是 she 的最长的后缀所以我们连接 e2-e这样我们假设从e2无法再继续伸展的时候我们就可以O(1)找到类似的串然后继续进行伸展得到如下的图 这样比如我们匹配sher的时候我们首先沿着边走到e2然后不需要重新搜索而是选择立即跳转到e节点然后搜索到r节点 这样我们就构造出了一个AC自动机的图 构建方法 就使用上面的例子 对于这样的一个图我们首先队列中有 Queue01hs同时将深度为1的节点连接Fail到root 然后我们扫描一遍h节点可以得到e节点然后我们扫描s节点可以发现s的Fail边上的root节点存在和s的儿子h相同的另一个h那么因为s的fail边上的所有节点的后缀相同所以我们有h2和h节点同时增加一个节点后仍然满足上面的Fail边的概念所以我们h2-h得到 同时我们的队列变成了 Queue012h2对于下面的伸展我们可以得到同理 呵呵呵代码时间 代码 void Insert(char *s){int len strlen(s), u root;for(int i0;ilen;i){int id idx(s[i]);if(!pool[u].ch[id]) pool[u].ch[id] ecnt;u pool[u].ch[id];}pool[u].End_Flag;
}
void build(){queueint que;for(int i0;i26;i)if(pool[root].ch[i])que.push(pool[root].ch[i]);int u, v, t, p;while(!que.empty()){u que.front();que.pop();for(int i0;iMAXK;i) if(pool[u].ch[i]){v pool[u].ch[i];que.push(v);p pool[u].Fail;while(p !pool[p].ch[i]) p pool[p].Fail;t pool[p].ch[i];pool[v].Fail t;pool[v].last pool[t].End_Flag ? t : pool[t].last;}}
} 感谢 感谢您阅读这篇文章如果有不足的地方请做出评论谢谢 转载于:https://www.cnblogs.com/JeremyGJY/p/5921588.html
