《KMP算法的应用.docVIP

01求子串在母串中所有出现的位置 给定主串S和模式串T，求T串在S串中所有出现的位置，允许不同位置的T串有部分重叠。例如：S=abababab，T=abab，T在S中出现的总次数就是3次（包括1、3、5三个起点位置，虽然S[1..4]与S[3..6]有部分重叠，但这是允许的）。输入信息包括两行，第一行为S串，第二行为T串；按从小到大的顺序输出所有T串出现的位置。 样例： 输入： 输出： abababab abab 1 3 5 02求多字符串的最长公共子串（POW） 给定n个字符串，求这n个字符串的最长公共子串。例如给3个字符串：abcb、bca和acbc，则这三个字符串的最长公共子串即为bc。输入第一行为n，下面n行即为这n个字符串。输出它们的最长公共子串。 样例： 输入： 输出： 3 abcb bca acbc bc 03最长回文子串问题 顺序和逆序相同的字符串便是回文串（例如’aba’）。求一个字符串所有的子串中最长的回文串便是最长回文子串问题。输入内容为一个字符串，输出它的最长回文子串。 样例： 输入： 输出： ababcbaab abcba 04 L-Gap子串问题（gap.pas） 如果一个字串形如UVU,U非空，且V恰好有L个字符，我们就称这种UVU形式的字串是一个L-Gap串。例如， abcbabc是 1-Gap 字串， xyxyxyxyxy 既可以是一个 2-Gap字串，也可以是一个6-Gap字串,但它不是一个10-Gap字串 (因为 U 必须非空)。 现在的问题时，给定一个字串s和一个正整数g, 请你在s串中找出所有的g-Gap子串，并输出所有的g-Gap子串总数。规定s串仅由小写字母组成，且其长度不超过50,000。 输入：Input 第一行为一个数字 t(1=t=10),表示测试点的个数 。以后的t行，每行有一个数字g(1=g=10) 和一个字串 s。 输出： 对于每一组数据，输出该组数据中所包含的 g-Gap 子串的数目。 示例： 输入： 输出： 2 7 1 bbaabaaaaa 1 5 abxxxxxab [注] L-Gap Substrings 标准算法是 二分+扩展KMP 或者 后缀树 我用的是ZhouYuan教我的O(n^2)加常数优化的方法 UvU形式 , 枚举长度U的长度L , 设数组B,如果S[i] = S[i + g + L],那么B[i]为1 , 否则B[i]为0。 如果存在连续L个1，那么就是答案了。先比较前L个，如果都是1，那么就是答案，继续比较。 如果在第i的位置出现了一个0，那么下一个有可能的答案的开始位置至少是i+1了。这个算法大约是答案级别的。 然后想，如果答案比较大，必然是重复串比较多。设F[i][k]表示i开始长度为k的循环串循环了多少次。k = 1..10. 通过这个预处理有一些答案就可以直接算而不需要比较了。经试验，只需要计算k=1的情况程序速度就已经非常快了。 05病毒（Timelimit ：0.5S Name：Virus） 一天TZ的电脑遭到了病毒袭击，他的硬盘空间一下子就被占满了。于是他找到了计算机组的“暴力杀病毒”——LQS，请他来帮忙。LQS研究了一下，发现这个病毒复制的文件都包含一长的01串，并且每个01串都包含了一个固定的子串。在同一个硬盘内，复制的01串是不可能相同的，所以说，该病毒并不会无限制的复制。由于人称“暴力杀病毒”，LQS很轻松的杀掉了该病毒。不过TZ对该病毒产生了浓厚的兴趣，他想计算一下，如果不考虑占满硬盘空间，在同一个硬盘里面，该病毒最多可以复制多少份？他本来想请LQS来帮他解决这个问题，可是LQS说：我要暴力搞密码！看来现在只好请聪明的你来帮他解决这个难题了。 输入 第一行母串长度N和子串长度M（1=M=N=2000）。 第二行为一个长度为M的01串，即每个母串应包含的子串。 输出 满足条件的母串个数。由于这个值可能很大，所以只要你输出其除以10000的余数。 样例输入 3 210样例输出 4 06 [注] 我们可以采用补集转化思想。因为长度为N的二进制串个数是很容易算出的。所以，如果求出这些串中间有多少个不包含给定的子串，也就等于求出了有多少个包含了给定的子串。 假定给定的子串为St。令f[i,j]表示符合下列两个条件的串S的数目。　　　（1） S的长度为i。　　　（2） S[I-J+1]..S[I]=St[1]..St[J]。且j是满足该式最大的一个。 根