前言 今天学习了一个新算法:KMP算法 其实很久以前学过早忘了 KMP算法是用于处理字串问题的算法。 参考Matrix67的博客:KMP算法详解|Matrix67 KMP算法的原理 假设有字符串A和B,要求判断B是否是A的字串 其实就是对于每个i,求最大的j,使得 Ai−j+1→i与B1→j 一一匹配 能匹配j指针就往后跳一个 否则就需要往回退 如下图: 我们希望往回退得越少越好, 通过上图可以发现,其实最佳方案就是 最长相同前后缀 对字符串B的每个前缀字串,找一个最长的长度l,使得长度为l的前后缀相同 这个可以预…

2017年8月1日 0条评论 0点热度 阅读全文

何为Trie树? 先容我吐槽一下这个数据结构的名字…… /ˈtriː/?/ˈtraɪ/?傻傻分不清楚 Trie树,又称字典树,是一种树形数据结构 被广泛用于字符串的统计 Trie树的构造 Trie树节点的每个儿子都代表一个字母 那么就可以用某节点到根的路径来表示一个字符串 如下图: (这颗Trie树保存了8个字符串:”A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”) 代码实现: struct node{ node *s[27]; int cnt; node () {}…

2017年6月11日 0条评论 0点热度 阅读全文

3942题解: 定义f[i] 为S串以第i位结尾的后缀,最长可以是T串多长的前缀,这一个可以用KMP匹配。 可以用一个first数组记录i字符前一个未被匹配的位置是哪一个,当f[i]=len(T)时,就可以将最末尾的len(T)个字符匹配了。 3940只需要把KMP换为AC自动机就可以。 3942: #include<cstdio> #include<cstring> #include<iostream> #define maxn 1000005 using namespace …

2017年4月15日 0条评论 0点热度 阅读全文