hdoj3746

这题先放上代码,回头继续琢磨,不明白为什么可以ac,用kmp求最小循环节的方法做的,好吧,其实只是试试看,结果居然能AC。。
————————————————————————————华丽的分割线————————————————
刚才去外面吃了一碗面,吃面的时候突然想明白了。原先一直认为直接用next数组做求出最小循环节后算出后面应该补上几个的做法不对。原因是在想这样一个问题:会不会在字符串后面补上更少(相比前面所述)的字符后形成的环就可以是有循环的环了,只不过此时循环的开始不是原字符串的开始。
实际上现在想想这个问题是非常傻的(不知道为什么做题的时候总是会出现各种类似问题),反证一下,加入上述情况成立,那么其实无论在环的哪里断开,形成的都会是有周期的,这样的话在原来的字符串的开始处断开也应得到周期串,那么补上的字符数不就等于“直接用next数组做求出最小循环节后算出后面应该补上几个”这种做法补上的字符数。矛盾。可见上述问题其实是由于考虑不全造成的庸人自扰。。
题目又说,可以在源字符串的前面添加字符,那么是否可以在前面加和后面同时加字符,这样优于只在后面不足最小循环节呢?呵呵。。其实这个问题就是上面的问题。假设按前者形成环,在原字符串开始处断开形成的字符串也是周期串,这样不就等于在后面补足吗。
说到底,上述这些问题源于对”一个循环的字符环无论在哪断开形成的都是周期串”这一点模糊。

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;
}