小胡同的诗

题目链接：hdu4763 题面 题目大意 找到字符串中的最长公共前后缀，并且这个前后缀的字串在除了前后缀的中间部分也要存在这个子串。例如：EAEBE，其中，E 表示这个子串，输出 E 的最大长度，如果不存在输出 0 。 解题思路 KMP 利用求失配函数得到串的最长公共前后缀，然后从 2i 的位置到 len-i 的位置开始枚举中间是否存在子串，判断条件是： fail[j]==ifail[j]==ifail[j]==i。含义是失配指针能够索引到公共前缀后一个位置，然后从 j 位置到达 i 表示 0 - j

场景 当有一段已知足够长的字符串T以及一段相对而言较小的字符串P，而问题是要让你统计P在T中出现的次数或者位置等这类匹配的问题。由于朴素匹配的时间复杂度不足以解决该问题时，可以尝试用kmp匹配算法。 原理及算法过程 我们发现朴素匹配算法之所以复杂度高，是因为做了许多不必要的回溯查找，而这些回溯过程，如果有存在循环节，则直接从循环节的对称点开始匹配，这样就把一些不必要的回溯跳过了。而这些不必要的匹...

题目大意: 给一段长度为n的整数s1以及相对较小长度为m的整数s2，问在s1中s2第一个成功匹配的位置在哪？不存在输出-1. 解题思路: kmp模板 AC代码: #include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <al...

题目大意: 给两个串s1,s2。问s1在s2中成功匹配的次数。 解题思路: RT. AC代码: #include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <algorithm> using namespace std; ...

题目大意: 给两个串s1,s2。问s2能不能和s1循环移动n次(n>=0)的串中匹配成功。 解题思路: 硬模拟的话会超时，复杂度接近O(n^2)。由于循环移动之后的状态一定属于两个s1拼接后的其中一个字串。于是按此操作AC。复杂度O(2*n-1+m)。这题利用拼接的技巧似乎模式串匹配直接用strstr也能完成。效率也蛮高- - AC代码: kmp: #include <stdio.h...

题目链接: HDU1358 题目大意: 给一段长度为n的字符串，让你求出长度为s的完美前缀字串(含k段循环节)的字串长度len以及循环次数k，k取最大(即循环节长度取最小) 解题思路: 关于next数组性质的应用 /** * HDU_1358 * * 输入: n以及长度为n的串。0表示输入结束 * 输出：循环节的长度以及循环的周期（循环周期取最大） * */ /** * * n...

（原创）详解KMP算法 KMP算法应该是每一本《数据结构》书都会讲的，算是知名度最高的算法之一了，但很可惜，我大二那年压根就没看懂过~~~ 之后也在很多地方也都经常看到讲解KMP算法的文章，看久了好像也知道是怎么一回事，但总感觉有些地方自己还是没有完全懂明白。这两天花了点时间总结一下，有点小体会，我希望可以通过我自己的语言来把这个算法的一些细节...

题目链接：hdu3336 题目大意：给一串n长度的字符串str，问str所有前缀(包括本串)在str中的匹配次数。 解题思路：利用kmp爆搜得到一发TLE，参考kmp+dp 以及dp状态方程解释博客思路学会利用next数组的性质进行dp优化：next[i]表示不包含下标为i的字符（i下标之前的串）的最长前后缀相等长度，那么我们设dp[i]表示以第i个字符为结尾 (或者说长度为i)的前缀能够匹配到的...

解题报告：问Alice的串是否能通过反转以及整除10的操作达到和Bob的串一样。相当于Bob的串只要是Alice的串的子串Alice就能赢。特别的，Bob的串为0的话Alice一定能赢！ Code： #include <stdio.h> #include <string.h> using namespace std; const int maxn = (int)1e5+5;...