题意:给出两个字符串,然你判断第一个字符串在第二个字符串中出现的次数。 思路:一个裸的KMP算法。主要内容在下面代码中实现。 #include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <string> using namespace std; int n; const int maxn = 1e4 + 5; char a[maxn * 100…

2018年4月16日 0条评论 0点热度 阅读全文

    很不错的一道字典树的题,把字典里的单词建成Trie树,每个节点维护一个以这个节点为根的子树有多少个单词,还有一个是当前节点有没有在这次询问中被搜索到,然后匹配的时候每次达到询问串的终点时把这个点标记一下,搜索过程中遇到的点也标记一下,然后再DFS一遍,这样保证不会搜索到字符串未遍历过的点,这个剪枝很重要。       #include<cstdio> #include<iostream> #include<cstring>…

2013年11月18日 0条评论 5点热度 阅读全文

kmp next函数 kmp的周期问题,深入了解kmp中next的原理 ----------------------- ----------------------- k    m        x      j       i 由上,next【i】=j,两段红色的字符串相等(两个字符串完全相等),s[k..…

2013年11月1日 0条评论 0点热度 阅读全文