参考
https://www.cnblogs.com/ycx-akioi/p/Z-algorithm.html
https://www.cnblogs.com/micrari/p/5585984.html

字符串匹配当中算法很多，对于不同的特征的字符串不同的算法表现也有差异，比如对于字符串中出现的字符种类很少而字串很长（如01序列）的时候，KMP算法表现比较好。这儿介绍的Z算法也是一种与KMP类似的一种字符串匹配算法，Z算法当中有个状态数组，叫作Z-数组，是我们需要计算的关键。

对于字符串S，我们有Z-数组z[]，其中z-数组中第i位的数值表示从第i位开始与字符串S的开头能完全匹配的长度。z[0]=strlen(S)是显然的，因为从第1位开始与字符串S匹配，整个串S都能完成匹配。以atbadcatbag为例，Z-数组z[]为{11,0,0,1,0,0,4,0,0,1,0}

对于Z-数组，我们将维护一个区间[lwbd,upbd]，对于lwbd>1的z[lwbd]若不为0，则upbd=lwbd+z[lwbd]-1 .这个区间[lwbd,upbd]所表示的子串就是与原字符串的头部匹配的子串。

Z数组可以对每一位分别与头部比较，但时间为O(|S|²)。可以采取一种方法仅用O(|S|)的时间就可以计算出Z-数组。

用类似递推的方法，假定已经知道了z[2,…,i-1]与upbd值最大的区间[lwbd,upbd]，要计算z[i]并且更新[lwbd,upbd]

[1]如果upbd<i，表示之前匹配过的长子串与当前第i位没有关联，就从第i位开始做枚举求z[i]。若z[i]不为0，则lwbd=i, upbd=lwbd+z[i]-1
[2]否则，记i’=i-lwbd+1,是区间[lwbd,upbd]跨过i平移到后边i的位置。此时会出现两种情况：
[2.1]若i+z[i’]<= upbd，则[i,i+z[i’]]是[lwbd,upbd]的一个真子区间。这样的话，从第i位与a的前缀匹配情况和从第i’位一样，所以z[i]=z[i’],lwbd与upbd不变
[2.2]而i+z[i’]>upbd的情况，i到upbd位的匹配与到upbd-lwbd+1位的匹配一样，即z[i]至少为upbd-i+1，就在此基础之上，从upbd+1位开始匹配，完成后lwbd=i,upbd=i+z[i]-1(此时z[i]必然不为0,这样写是可行的)

void genZBox(char *s)
{
	int z[N],lwbd,upbd,len,i,ii;
	memset(z,0,sizeof(z));
	lwbd=0;
	upbd=0;
	len=strlen(s);
	z[0]=len;
	for(i=1;s[i];i++)
	{
		if(upbd<i)
		{
			z[i]=0;
			while( i+z[i]<len && s[i+z[i]]==s[z[i]])
				z[i]++;
			if(z[i]>0)
			{
				lwbd=i;
				upbd=i+z[i]-1;
			}
		}
		else
		{
			ii=i-lwbd+1;
			if(ii<=upbd)
				z[i]=z[ii];
			else
			{
				z[i]=upbd-i+1;
				while(i+z[i]<len && s[i+z[i]]== s[z[i]])
					z[i]++;
				lwbd=i;
				upbd=i+z[i]-1;
			}
		}
	}
	for(i=0;i<len;++i)
	{
		printf("%4d",z[i]);
	}
	printf("\n");
}