686. 重复叠加字符串匹配

kmp函数套着用

void nex(char *s, int *next)
{
    next[0] = 0;
    int now = 0, x = 1;
    while (x < strlen(s))
    {
        if (s[now] == s[x])
        {
            now+=1;
            next[x] = now;
            x += 1;
        }
        else if (now)
        {
            now = next[now - 1];
        }
        else
        {
            next[x] = 0;
            x += 1;
        }
    }
}

int kmp(char *s,char *p){
    int *next = NULL;
    next = (int *)malloc(sizeof(int) * strlen(p));
    nex(p, next);
    int now = 0, px = 0;
    while (now < strlen(s))
    {
        if (p[px] == s[now])
        {
            px += 1;
            now += 1;
        }
        else if (px)
            px = next[px - 1];
        else
            now += 1;
        if (px == strlen(p))
        {
            return 1;
        }
    }
    return 0;
}

int repeatedStringMatch(char * a, char * b){
char ans[1000000]="";
int res=0;
while(strlen(ans)<strlen(b)){
    strcat(ans,a);
    res+=1;
}
if(kmp(ans,b))
return res;
else strcat(ans,a);
res+=1;
if(kmp(ans,b))
return res;
else return -1;
}