「JSOI2012」玄武密码

2021-04-18 11:28

阅读：419

标签：自动机节点 read insert str 表示 stat == online

「JSOI2012」玄武密码

传送门

题目是要求多个串在母串上的最长匹配长度。

考虑 \(\text{AC}\) 自动机，我们建出 \(\text{Trie}\) 图然后用母串来在上面跑。

每一个能匹配的位置，它 \(\text{fail}\) 的位置也一定可以匹配，我们就跳 \(\text{fail}\) 把经过的节点的值赋为 \(1\) ，表示这个位置可以匹配。

然后我们每一个模式串，找到ta在 \(\text{Trie}\) 树上最深的可以匹配的节点来计算答案即可。

参考代码：

#include 
#include 
#define rg register
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
template  inline void read(T& s) {
    s = 0; int f = 0; char c = getchar();
    while ('0' > c || c > '9') f |= c == '-', c = getchar();
    while ('0'

「JSOI2012」玄武密码

标签：自动机节点 read insert str 表示 stat == online

原文地址：https://www.cnblogs.com/zsbzsb/p/12283521.html

上一篇：博客美化代码，坐等js权限

下一篇：php为什么要使用swoole

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：「JSOI2012」玄武密码
文章链接：http://soscw.com/index.php/essay/76266.html

亲，登录后才可以留言！

「JSOI2012」玄武密码

「JSOI2012」玄武密码

评论

热门文章

推荐文章

最新文章

置顶文章