leetcode 686.重复叠加字符串 KMP方法（C语言实现）

题目描述：

给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。

注意：字符串 "abc" 重复叠加 0 次是 ""，重复叠加 1 次是 "abc"，重复叠加 2 次是 "abcabc"。

示例 1：

输入：a = "abcd", b = "cdabcdab"
输出：3
解释：a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。
示例 2：

输入：a = "a", b = "aa"
输出：2
示例 3：

输入：a = "a", b = "a"
输出：1
示例 4：

输入：a = "abc", b = "wxyz"
输出：-1
 

提示：

1 <= a.length <= 104
1 <= b.length <= 104
a 和 b 由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/repeated-string-match
 

代码：

void Getnext(int* next, char* sub)
{
	int len = strlen(sub);
	next[0] = -1;
	next[1] = 0;
	int i = 2;//从next[2]开始遍历
	int k = 0;
	while (i < len)
	{
		//i一直往前走，k可以变换
		if ((k == -1) || (sub[k] == sub[i - 1]))//因为数组整体往右加一
		{
			//当sub[k] == sub[i]
			//next[i+1] == k + 1 
			next[i] = k + 1;
			i++;
			k++;
		}
		else
		{
			k = next[k];
		}
	}
}
int kmp(char* str, char* sub)//在str中匹配sub,若成功返回序号，失败返回-1
{
	//str为主串,sub为子串
	if (strlen(str) < strlen(sub))
	{
		return -1;
	}
	int i = 0;
	int j = 0;
	int lenstr = strlen(str);
	int lensub = strlen(sub);
	int* next = (int*)malloc(sizeof(int) * lenstr);
	Getnext(next, sub);
	while (i < lenstr && j < lensub)
	{
		if ((j == -1) || (sub[j] == str[i]))
		{
			//j == -1时next[0] = -1
			j++;
			i++;
		}
		else
		{
			j = next[j];
		}
	}
	free(next);
	if (j >= lensub)
	{
		return i - j;
	}
	return -1;

}
int repeatedStringMatch(char * a, char * b)
{
	if(strcmp(a,b)==0)
    {
       return 1;
    }
    char c[100000];
	strcpy(c, a);
	int i = 1;
	while (kmp(c,b) ==-1 && strlen(c) <= 2 * strlen(a) + strlen(b))
	{
		strcat(c, a);
		i++;
	}
	if (strlen(c) <= 2 * strlen(a) + strlen(b))
		return i;
	else
		return -1;
}