寒假集训——KMP

发布时间:2017-2-20 0:36:39 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"寒假集训——KMP",主要涉及到寒假集训——KMP方面的内容,对于寒假集训——KMP感兴趣的同学可以参考一下。

此文章是集训题目的解题报告,另外自己网上找了一些KMP的题目做做。 KMP简单应用 Time Limit: 1000MS Memory limit: 65536K 题目描述 给定两个字符串string1和string2,判断string2是否为string1的子串。 输入  输入包含多组数据,每组测试数据包含两行,第一行代表string1(长度小于1000000),第二行代表string2(长度小于1000000),string1和string2中保证不出现空格。 输出  对于每组输入数据,若string2是string1的子串,则输出string2在string1中的位置,若不是,输出-1。 示例输入 abc a 123456 45 abc ddd 示例输出 1 4 -1 提示 解题报告 关于KMP报告在上一篇文章写了,这边就不详细写了,这题因为是用KMP来解的,所以数据很大,要注意的地方就是在循环的时候不能用strlen函数,不然每次循环都会耗掉调用函数的时间。。。 #include<stdio.h> #include<string.h> int next[1000010]; char T[1000010],B[1000010]; void getNext()//next数组 { int m=strlen(B); int i=0,j=-1; next[0]=-1; while(i<m) { if(j==-1||B[i]==B[j]) { i++;j++; next[i]=j; } else j=next[j]; } } int kmp()//KMP算法 { getNext(); int n=strlen(T),m=strlen(B); int i=0,j=0; while(i<n&&j<m) { if(j==-1||T[i]==B[j]) { i++;j++; } else j=next[j]; } if(j==m) return i-m+1; else return -1; } int main() { while(scanf("%s%s",T,B)!=EOF) { printf("%d\n",kmp()); } return 0; } Power Strings Time Limit: 1000MS Memory limit: 65536K 题目描述 Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n). 输入  Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case. 输出  For each s you should print the largest n such that s = a^n for some string a. 示例输入 abcd aaaa ababab . 示例输出 1 4 3 提示  This problem has huge input, use scanf instead of cin to avoid time limit exceed. 解题报告 题目的意思是一个字符串能用若干连续子串组成,也就是循环节问题,求最大循环节,如ababab的循环节ab,最大3个。。。 这题目是运用KMP算法中的next数组来解题,next数组是部分匹配表,它是记录字符串前缀和后缀的最长的公共子串长度。 #include<stdio.h> #include<string.h> int next[1000010]; char B[1000010]; void getNext() { int i=0,j=-1; next[0]=-1; int l=strlen(B); while(i<l) { if(j==-1||B[i]==B[j]) { i++;j++; next[i]=j; } else j=next[j]; } }/* void getNextval() { int i=1,j=0; next[1]=0; int l=strlen(B); while(i<=l) { if(j==0 || B[i]==B[j]) { ++i;++j; if(B[i]!=B[j]) next[i]=j; else next[i]=next[j]; } else j=next[j]; } }*/ int main() { int i,j,f; while(~scanf("%s",B)) { if(B[0]=='.')break; int l=strlen(B); getNext();//for(int i=1;i<=l;i++)printf("%d",next[i]); //printf("\n"); if(l%(l-next[l])==0)printf("%d\n",l/(l-next[l])); else printf("1\n"); } } Period Time Limit: 1000MS Memory limit: 65536K 题目描述 For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 ≤ i ≤ N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as AK , that is A concatenated K times, for some string A. Of course, we also want to know the period K.   输入  The input file consists of several test cases. Each test case consists of two lines. The first one contains N (2 <= N <= 1 000 000) – the size of the string S. The second line contains the string S. The input file ends with a line, having the number zero on it.   输出  For each test case, output “Test case #” and the consecutive test case number on a single line; then, for each prefix with length i that has a period K > 1, output the prefix size i and the period K separated by a single space; the prefix sizes must be in increasing order. Print a blank line after each test case.   示例输入 3 aaa 12 aabaabaabaab 0 示例输出 Test case #1 2 2 3 3 Test case #2 2 2 6 2 9 3 12 4 解题报告 这题就是在上一题进行变化,贴代码。。。PE一次。。。 #include<stdio.h> #include<string.h> int next[1000010],n; char B[1000010]; void getNext() { int i=0,j=-1; next[0]=-1; int l=strlen(B); while(i<l) { if(j==-1||B[i]==B[j]) { i++;j++; next[i]=j; } else j=next[j]; } } int main() { int i=1; while(scanf("%d",&n)!=EOF&&n) { //getchar(); scanf("%s",B); getNext(); printf("Test case #%d\n",i++); for(int k=2;k<=n;k++) { if(k%(k-next[k])==0&&k/(k-next[k])!=1)printf("%d %d\n",k,k/(k-next[k])); } printf("\n"); } }

上一篇:优化网站配置
下一篇:前端开发攻城师绝对不可忽视的五个HTML5新特性

相关文章

相关评论