题意:问模式串在文本串中出现的次数,不允许重叠。
思路:kmp,关键在于不允许重叠。。。
其实只要每次找到的时候j=0一下就好咯。
/* *********************************************** Author :111qqz Created Time :2016年08月11日 星期四 02时52分44秒 File Name :code/hdu/2087.cpp ************************************************ */
1#include <cstdio> 2#include <cstring> …
阅读更多题意:求出所有的前缀和后缀相同的子串的长度。
思路:求出nxt函数,观察发现,从从len递归向前就是答案。
/* *********************************************** Author :111qqz Created Time :2016年08月10日 星期三 21时05分52秒 File Name :code/poj/2752.cpp ************************************************ */
1#include <cstdio> 2#include <cstring> 3#include …
阅读更多题意:给定一个字符串 L,已知这个字符串是由某个字符串 S 重复 R 次而得到的, 求 R 的最大值
思路:论文题.
转载论文中的题解:
做法比较简单,穷举字符串 S 的长度 k,然后判断是否满足。判断的时候, 先看字符串 L 的长度能否被 k 整除,**再看 suffix(1)和 suffix(k+1)的最长公共** **前缀是否等于 n-k**。在询问最长公共前缀的时候,suffix(1)是固定的,所以 RMQ 问 题 没 有 必 要 做 所 有 的 预 处 理 , 只 需 求 出 height 数 组 中 的 每 一 个 数 到 height[rank[1]]之间的最小值即可。整个做法的时间复杂度为 O(n) …
阅读更多