Leetcode 686. KMP method of repeatedly superimposing strings (implemented in C language)

Title Description ：

Given two strings  a and b, Look for overlapping strings a The minimum number of times , Make string b Becomes the superimposed string a The string of , Returns if it does not exist -1.

Be careful ： character string "abc"  Repeat stack 0 Next is "", Repeat stack 1 Next is  "abc", Repeat stack 2 Next is  "abcabc".

Example 1：

Input ：a = "abcd", b = "cdabcdab"
Output ：3
explain ：a Repeat three times to get "abcdabcdabcd", here b It's a substring .
Example 2：

Input ：a = "a", b = "aa"
Output ：2
Example 3：

Input ：a = "a", b = "a"
Output ：1
Example 4：

Input ：a = "abc", b = "wxyz"
Output ：-1
 

Tips ：

1 <= a.length <= 104
1 <= b.length <= 104
a and b It's made up of lowercase letters

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/repeated-string-match
 

Code ：

void Getnext(int* next, char* sub)
{
	int len = strlen(sub);
	next[0] = -1;
	next[1] = 0;
	int i = 2;// from next[2] To traverse the 
	int k = 0;
	while (i < len)
	{
		//i Go straight ahead ,k You can change 
		if ((k == -1) || (sub[k] == sub[i - 1]))// Because the whole array adds one to the right 
		{
			// When 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)// stay str Match sub, If successful, return the serial number , Failure to return -1
{
	//str Main string ,sub For substrings 
	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 when 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;
}