c语言，这个kmp算法有问题吗，运行后死循环

Question

c语言，这个kmp算法有问题吗，运行后死循环

void GetNext(int* next,char* sub,int subl){  //next[i]记录了sub[i]前，不包括自己的最长公共前后缀
    next[0]=0;
    int i=0;
    int j=1;
    int l=0;
    while(i<subl-1){
        if(sub[i]==sub[j]){
            i++;
            j++;
            l++;
            next[j]=l;
        }
        else if(i==0){
            next[j]=0;
            j++;
        }
        else{
            i=next[i];
            l=next[i];
        }
    }
}

int KMP1(char* str,char* sub,int strl,int subl){  //没用到nextval数组
    int* next=(int*)malloc(sizeof(int)*subl);
    GetNext(next,sub,subl);
    int i,j;
    i=j=0;
    while(i<strl&&j<subl){
        if(str[i]==str[j]){
            i++;
            j++;
        }
        else{
            j=next[j];
        }
    }
    free(next);
    if(j==subl){
        return i-subl;
    }
    return -1;
}

Answer 1

在这个 KMP 算法中，当 sub 中第一个字符与 str 中的某个字符不匹配时，会将 j 更新为 next[j]，但是在某些情况下，next[j] 可能会更新为 j，导致出现死循环的情况。具体来说，当 sub 中存在连续相同的字符时，next[j] 就会被更新为 j，从而导致死循环。

为了解决这个问题，你可以将 GetNext() 函数中的代码做如下修改：

void GetNext(int* next,char* sub,int subl){
    next[0]=0;
    int i=0;
    int j=1;
    int l=0;
    while(j<subl){
        if(sub[i]==sub[j]){
            i++;
            j++;
            l++;
            next[j]=l;
        }
        else if(i==0){
            next[j]=0;
            j++;
        }
        else{
            i=next[i];
            l=next[i];
        }
    }
}

这样修改后，当 sub 中存在连续相同的字符时，next[j] 仍然会被更新为 j，但是此时 i 的值也会被更新为 j，从而避免了死循环的情况。

另外，你在 KMP1() 函数中使用了 malloc() 分配内存，但是没有在函数结束后释放内存，这可能会导致内存泄漏。为了避免这个问题，你可以在函数结束后使用 free() 释放 next 数组的内存，例如：

int KMP1(char* str,char* sub,int strl,int subl){
    int* next=(int*)malloc(sizeof(int)*subl);
    GetNext(next,sub,subl);
    int i,j;
    i=j=0;
    while(i<strl&&j<subl){
        if(str[i]==str[j]){
            i++;
            j++;
        }
        else{
            j=next[j];
        }
    }
    int result = -1;
    if(j==subl){
        result = i-subl;
    }
    free(next);
    return result;
}

这样，就避免了内存泄漏的问题。