hdu 2087 题目链接 题意：问模式串在文本串中出现的次数，不允许重叠。 思路：kmp，关键在于不允许重叠。。。 其实只要每次找到的时候j=0一下就好咯。 /* *********************************************** Author :111qqz Created Time :2016年08月11日 星期四 02时52分44秒 File Name :code/hdu/2087.cpp ************************************************ */ #include <cstdio> #include <cstring> …

hdu 1711 题目链接 题意：给定两个数列，问第二个数列在第一个数列中出现的位置（第一个元素对应的位置） 思路：数列也可以看成字符串，然后左kmp，返回的答案是i+1-m。。。1A /* *********************************************** Author :111qqz Created Time :2016年08月11日 星期四 02时30分23秒 File Name :code/hdu/1711.cpp ************************************************ */ #include <cstdio> #include …

poj 3080 题目链接 题意：给出n个字符串（n<=10），字符串长度不超过70，问出现在全部n个字符串中的最长并且字典序最小的长度大于等于3的子串。 思路：数据范围很小。。。直接暴力枚举+kmp匹配一下。。。 /* *********************************************** Author :111qqz Created Time :2016年08月11日 星期四 01时29分02秒 File Name :code/poj/3080.cpp ************************************************ */ #include …

poj 2185 题目链接 题意：给出一个字符矩形，问一个面积最小的矩形，覆盖掉整个矩形。大概就是二维的最小覆盖子串。 思路：对于每一行做最小覆盖子串，然后求lcm，每一列也是如此。最后记得判断不能超过原有的n,m。 /* *********************************************** Author :111qqz Created Time :2016年08月10日 星期三 23时46分47秒 File Name :code/poj/2185.cpp ************************************************ */ #include <cstdio> …

参考资料（本文大部分是参考这篇博客，附带一些证明步骤的解释） 首先明确一些概念： 最小覆盖子串：对于某个字符串s，它的最小覆盖子串指的是长度最小的子串p，p满足通过自身的多次连接得到q，最后能够使s成为q的子串。 比如： 对于s="abcab"，它的最小覆盖子串p="abc"，因为p通过在它后面再接上一个p（即重叠0个字符），可以得到q="abcabc"，此时s是q的子串。 对于s="ababab"，它的最小覆盖子串为p="ab"。 pre[i]（或next[i]）的实质是串str[1..i]的最长且小于i的“相等前、后缀”分别 …

poj 2752题目链接 题意：求出所有的前缀和后缀相同的子串的长度。 思路:求出nxt函数，观察发现，从从len递归向前就是答案。 /* *********************************************** Author :111qqz Created Time :2016年08月10日 星期三 21时05分52秒 File Name :code/poj/2752.cpp ************************************************ */ #include <cstdio> #include <cstring> #include …

hdu1686 题意：给出模式串和文本串，问模式串在文本串中出现了多少次，可以overlap. 思路：思考naive的匹配过程。nxt函数不过是改进了当失配发生时，不是移动1位，而是移动多位。nxt函数的含义是当失配发生时，移动到的位置....所以有的教程管这个叫失配函数吧，也不是很难理解的样子。 学会kmp之后的第一道kmp，嘿嘿嘿（是的，poj2406的时候我并不会kmp 2333) /* *********************************************** Author :111qqz Created Time :2016年08月10日 星期三 20时02分33秒 File Name …

20170801update:当时竟然没有强调next函数的含义？ next[i]的含义是,i之前的整个前缀中，最长的该前缀的前缀和后缀相同的长度。 看图： KMP感觉是我学到现在最难懂的一个算法了QAQ 为什么你们都那么强啊，看几个小时就看懂了... 先放一波我觉得值得看的资料： kmp算法讲解（配图比较全....） kmp学习资料2 说下我对kmp算法的理解： 理解kmp算法大概分成两个部分。 一部分是理解一个naive的kmp算法，可以叫"fast slide" algorithm 思想大概就是，当mismatch发生时，我们并不是一无所有，而是知道在mismatch发生前所匹配的字符的信息的。 然后知 …

poj 2406 题意:给定一个字符串 L,已知这个字符串是由某个字符串 S 重复 R 次而得到的, 求 R 的最大值 思路:论文题. 转载论文中的题解: 做法比较简单,穷举字符串 S 的长度 k,然后判断是否满足。判断的时候, 先看字符串 L 的长度能否被 k 整除,**再看 suffix(1)和 suffix(k+1)的最长公共** **前缀是否等于 n-k**。在询问最长公共前缀的时候,suffix(1)是固定的,所以 RMQ 问 题 没 有 必 要 做 所 有 的 预 处 理 , 只 需 求 出 height 数 组 中 的 每 一 个 数 到 height[rank[1]]之间的最小值即可。整个做法的时间复杂度为 O(n) …