HDU-3746 Cyclic Nacklace

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3746

题目大意：

给你一个字符串，要求将字符串的全部字符最少循环2次需要添加的字符数。

例子：

abcabc 已经循环2次，添加数为0

abcac 没有循环2次，添加字符abcac。数目为5.

abcabcab 已经循环过2次，但第三次不完整，需要添加数为1

解题思路：

next[]数组的运用。

这里需要深刻理解next数组的含义，所以需要花费一定的功夫去弄懂这些。。

对于next数组，经过3天的学习，有了一定的认识。自己总结一下吧。

首先，求next数组有两种方法。第一种是严蔚敏教授那本数据结构上的求法。代码如下：

void getnext(const char *s)
{
	int i = 0, j = -1;
	nextval[0] = -1;
	while(i != len)
	{
		if(j == -1 || s[i] == s[j])
			nextval[++i] = ++j;
		else
			j = nextval[j];
	}
}

这种求法的含义是：

next[i]代表了前缀和后缀的最大匹配的值（需要彻底明白这点，相当重要）

另外一种是对这种算法的改进版本，代码如下：

void getnext(const char *p) //前缀函数(滑步函数)
{
	int i = 0, j = -1;
	nextval[0] = -1;
	while(i != len)
	{
		if(j == -1 || p[i] == p[j]) //(全部不相等从新匹配 || 相等继续下次匹配)
		{
			++i, ++j;
			if(p[i] != p[j]) //abcdabce
				nextval[i] = j;
			else //abcabca
				nextval[i] = nextval[j];
		}
		else
			j = nextval[j]; //子串移动到第nextval[j]个字符和主串相应字符比较
	}
}

改进的地方在于-1的运用，关于怎么优化我已经写过了。自己看下就行了。。。但是一定要明白。

不同之处：

没有优化的getnext函数，next数组存的是前缀和后缀的最大匹配值，而优化后的getnext函数存的是在这个基础，进行更高效的改进。

比如abcabca

改进前最后一个字符next[7]=4,表示的是前缀和后缀最大匹配是4，即abca和abca。

改进后的next[7]=-1。这点也需要彻底搞懂，才能灵活的运用next函数。

总结一下：

在求前缀和后缀的最大匹配值时，要使用第一种，也就是未优化的算法。在运用KMP时，使用第二种算法，因为避免了多余的判断，更加高效。

YY：

其实我们可以发现KMP算法的精华部分是一个DP。每次右滑时，都是根据前面状态得到的有用信息进行的。相当于记忆化更新。这样算法才具有了很高的效率。

当然，理解这个算法确实需要仔细反复的研究，反正我是看了3天，才把这点基础东西搞的差不多，算是理解了80%吧。剩下的在以后做题的过程中慢慢发现吧。。。。

这道题的代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 100010

char s[N];
int nextval[N];
int len;

void getnext(const char *s)
{
	int i = 0, j = -1;
	nextval[0] = -1;
	while(i != len)
	{
		if(j == -1 || s[i] == s[j])
			nextval[++i] = ++j;
		else
			j = nextval[j];
	}
}

int main()
{
	int ncase;
	int length, add;
	scanf("%d", &ncase);
	while(ncase--)
	{
		scanf("%s", s);
		len = strlen(s);
		getnext(s);
		/*for(int i = 0; i <= len; ++i) //查看next数组的内容
			cout<<nextval[i]<<" ";
		cout<<endl;*/
		length = len - nextval[len]; //循环节的长度
		if(len != length && len % length == 0) //循环多次
			printf("0\n");
		else
		{
			add = length - nextval[len] % length; //取余的作用：abcab，去掉abc
			printf("%d\n",add);
		}
	}
	return 0;
}