C语言KMP算法实现模式匹配计算结果错误

Question

代码如下
https://pastebin.ubuntu.com/p/t5phNgjPXh/
无法输出正确结果，应该怎么改
判断命令行参数是否正确这么判断可以吗

Answer 1

给你答复了一遍了，get_next()函数这里存在两个风险，if语句中，i++和 j++后，给next[i]赋值，next数组 有越界的风险。第二点，else语句中，j=next[j]，i 的值不变，while存在死循环的风险。这个函数功能我看不懂，把问题告诉你，你自己改一下吧，其它部分的代码我修改了一下，如下：

#pragma warning(disable:4996)
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxsize 100
typedef int Status;
typedef struct _sstring{
    char* ch;
    Status length;
    _sstring() {
        ch = 0;
        length = 0;
    }
}SString;

Status StrAssign(SString T, char* chars)
{
    int i;
    if (T.ch)
        free(T.ch);
    char* c;
    for (i = 0, c = chars; *c; ++i, ++c);
    if (!i) {
        T.ch = NULL;
        T.length = 0;
        return 0;
    }
    else {
        if (!(T.ch = (char*)malloc((i+1) * sizeof(char))))
            exit(-1);
        for (int j = 0; j < i; j++) {
            T.ch[j] = chars[j];
            T.length = i;
        }
        T.ch[i] = 0;
        T.length = i;
        return 1;
    }
}//生成串

Status StrLength(SString S) {
    return S.length;
}//返回S的元素个数，称为串的长度

Status StrCompare(SString S, SString T) {
    int i;
    for (i = 0; i < S.length && i < T.length; ++i) {
        if (S.ch[i] != T.ch[i]) {
            return S.ch[i] - T.ch[i];
        }
        //return S.length - T.length;
    }
    if (i == S.length && i == T.length)
        return 0;
    else if (i == S.length && i < T.length)
        return -1;
    else
        return 1;
}//若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0。

void ClearString(SString S) {
    if (S.ch) {
        free(S.ch);
        S.ch = NULL;
    }
    S.length = 0;
}//将S清为空串，并释放S所有空间

void get_next(SString S, int next[]) {//求出模式串S的next函数值并存入数组next
    int i = 1, j;
    next[1] = 0;
    j = 0;
    while (i < S.length) {
        if (j == 0 || S.ch[i] == S.ch[j]) {
            i++;
            j++;
            next[i] = j;  //这里存在越界的风险
        }
        else {
            j = next[j]; //这里是否有问题？ i的值不变，while存在死循环的风险
        }
    }//get_next
}

int Index_KMP(SString S, SString T, int pos) {
    int i = pos;
    int j = 1;
    int next[maxsize];
    while (i <= S.length && j <= T.length) {
        if (j == 0 || S.ch[i] == T.ch[j]) {
            i++;
            j++;
        }
        else {
            get_next(S, next);
            j = next[j];
        }
    }
    if (j > T.length) {
        return i - T.length;
    }
    else {
        return 0;
    }
}

int main() {
    SString S, T;
    char* s, * t;
    //添加下面两句
    s = (char*)malloc(100);
    t = (char*)malloc(100);
    ClearString(S);
    ClearString(T);
    scanf("%s", s);
    scanf("%s", t);
    StrAssign(S, s);
    StrAssign(T, t);
    int pos = 0;
    pos = Index_KMP(S, T, pos);
    printf("%d", pos);
    return 0;
}