这题先放上代码,回头继续琢磨,不明白为什么可以ac,用kmp求最小循环节的方法做的,好吧,其实只是试试看,结果居然能AC。。
————————————————————————————华丽的分割线————————————————
刚才去外面吃了一碗面,吃面的时候突然想明白了。原先一直认为直接用next数组做求出最小循环节后算出后面应该补上几个的做法不对。原因是在想这样一个问题:会不会在字符串后面补上更少(相比前面所述)的字符后形成的环就可以是有循环的环了,只不过此时循环的开始不是原字符串的开始。
实际上现在想想这个问题是非常傻的(不知道为什么做题的时候总是会出现各种类似问题),反证一下,加入上述情况成立,那么其实无论在环的哪里断开,形成的都会是有周期的,这样的话在原来的字符串的开始处断开也应得到周期串,那么补上的字符数不就等于“直接用next数组做求出最小循环节后算出后面应该补上几个”这种做法补上的字符数。矛盾。可见上述问题其实是由于考虑不全造成的庸人自扰。。
题目又说,可以在源字符串的前面添加字符,那么是否可以在前面加和后面同时加字符,这样优于只在后面不足最小循环节呢?呵呵。。其实这个问题就是上面的问题。假设按前者形成环,在原字符串开始处断开形成的字符串也是周期串,这样不就等于在后面补足吗。
说到底,上述这些问题源于对”一个循环的字符环无论在哪断开形成的都是周期串”这一点模糊。
Category Archives: KMP
hdoj1867
这题和上一题一个思路,但是两个字符串可以调换顺序相接,这样就要求两次next数组。开始因为用上一题的方法分情况讨论,一直WA(其实原因是函数返回字符串指针的地方出了点错。。),上网找了资料,发现其实根本不用分情况讨论,只要两个字符串相接的时候中间加个特殊的字符即可,这样可以保证next[len1+len2+1]不会比其中任何一个字符串长(本来若是不加,则最长前缀可能超过第一个字符串长度,加了之后则限定在了两个字符串的长度范范围内)。
hdoj2594
求第一个字符串的最长前缀和第二个字符串的后缀相同,典型的next数组的应用,只要两个字符串接在一起即可。
本题情况比较多,要逐一考虑。注意k<=len1 && k>len2 还有k>len1 && k<=len2这两种情况,当tmp=(len1+len2)%(len1+len2-k)为0,也就是第二个字符串的后缀正好构成最小循环节时,此时答案不是0,而是要竟可能多的加上最小循环节circle,这个特殊情况注意。(不过开始没考虑这点,还是能AC。。)
hdoj2203
大概理解了kmp之后,写起来感觉好多了。这题很明显是kmp,因为数据量太大。但是问题是这题的主串太多,原文本串每循环移1位之后就形成了新的主串。仔细思考会发现把主串重复一遍接在后面作为新的唯一的主串,这样循环形成的主串全包含在里面了。
hdoj2087——KMP的应用
#include<stdio.h> #include<stdlib.h> #include<string.h> void get_next(char b[], int *next) { int i = 0; int j = -1; next[0] = -1; int len_b = strlen(b); while(i < len_b - 1) { if(j == -1 || b[i] == b[j]) { ++i; ++j; next[i] = j; } else { j = next[j]; } } return; } int kmp(char a[], char b[], int next[]) { int i = 0; int j = 0; int len_a = strlen(a); int len_b = strlen(b); while(i < len_a && j < len_b) { if(j == -1 || a[i] == b[j]) { ++i; ++j; } else { j = next[j]; } } if(j >= len_b) { return i - len_b; } else { return -1; } } int solve(char s[],char t[],int len,int next[]) { int ans=kmp(s,t,next); if(ans==-1) return 0; return 1+solve(s+ans+len,t,len,next); } int main() { char s[1010],t[1010]; scanf("%s",s); getchar(); while(strcmp("#",s)!=0) { gets(t); int next[1010]; get_next(t,next); int len=strlen(t); int ans=solve(s,t,len,next); printf("%d\n",ans); scanf("%s",s); getchar(); } //system("pause"); return 0; }
扩展KMP模板
next[i]:T[i..m]和T[0..m]的最长公共前缀长度
extend[i]:S[i..n]和T[0..m]的最长公共前缀长度
hdoj1358
循环节:len-next[len]为长度为len的字符串的循环节,特别的,当k=len%(len-next[len])==0时,该字符串含有k个周期。但当k!=0时说明最后一个循环节未满。
KMP模板(字符串都从0开始)(转载)
主串和模式串都从0开始
控制字符串输入起始指针:scanf(“%s”,s+1);
转载自:http://www.cnblogs.com/10jschen/archive/2012/08/19/2646381.html
KMP算法
详细原理请见严蔚敏、吴伟明是《数据结构》,关键是next数组的理解,这个有点绕,现在理解比较朦胧。放上代码