KMP算法的实现

道化師

#include <stdio.h>
#include <stdlib.h>

//给char * 起名为String
typedef char* String;

//定义一个结构体，str存储字符串，cap存储字符串的长度
typedef struct
{
        char str[255];
        int cap;
}Str;

//获取next数组，这个是KMP算法的灵魂
void get_next(Str *T, int *next )
{
        int j = 0;
        int i = 1;
        next[1] = 0;
        
        while( i < T->str[0] )   //当循环次数超过字符串的长度的时候退出循环
        {
                if( 0 == j || T->str[i] == T->str[j] )
                {
                        i++;
                        j++;
                        if( T->str[i] != T->str[j] )    //改进后的算法
                        {
                                next[i] = j;
                        }
                        else
                        {
                                next[i] = next[j];
                        }
                }
                else
                {
                        j = next[j];
                }
        }
}

// 返回子串T在主串S第pos个字符之后的位置
// 若不存在，则返回0
int Index_KMP( Str *S, Str *T, int pos )
{
        int i = pos;
        int j = 1;
        int next[255];
        
        get_next( T, next );
        
        while( i <= S->cap && j <= T->cap)
        {
        //增加判断，防止特殊情况发生
                if( 0 == j || S->str[i] == T->str[j] )
                {
                        i++;
                        j++;
                }
                else
                {
                        j = next[j];
                }
        }
        
        if( j > T->cap )
        {
                return i - T->cap;
        }
        else
        {
                return 0;
        }
}

//创建存储容量和字符串的结构，这里需要改变结构体的内容，所以传入指向指针的指针
void CreateStr(Str **S)
{
        *S = (Str *)malloc(sizeof (Str));
        if (!S)
        {
                perror("INIT:malloc");
                exit(EXIT_FAILURE);
        }
        
        printf("请输入一个字符串，输入回车结束：");
        char ch;
        int i = 0;
        
        while ((ch = getchar()) != '\n')
        {
                (*S)->str[i++] = ch;     //后置++，先赋值，后++
        }
        //这里i相当与字符串的长度
        (*S)->cap = i;
        
}

int main(void)
{
        Str *S = NULL;
        Str *T = NULL;
        int pos = 1;
        int status = 0;
        
        CreateStr(&S);
        CreateStr(&T);
        
        status = Index_KMP(S, T, pos);
        
        if (1 == status)
        {
                printf("是");
        }
        else
        {
                printf("否");        
        }
        

FishC

这段代码实现了KMP算法，用来查找子串在主串中的位置。不过代码中有一些错误和不完善的地方，我来帮你解决。

首先，在函数get_next()中，你需要将next定义为数组，而不是整数。next数组存储的是匹配失败时下一次比较的位置，所以它的长度应该与字符串T的长度相同。修改代码如下：

void get_next(Str *T, int *next )
{
        int j = 0;
        int i = 1;
        next[0] = 0; // 初始化next[0]为0
        
        while( i < T->cap )   //修改为cap
        {
                if( 0 == j || T->str[i-1] == T->str[j-1] ) // 修改为str[i-1]和str[j-1]
                {
                        i++;
                        j++;
                        if( T->str[i-1] != T->str[j-1] )    //改进后的算法
                        {
                                next[i] = j;
                        }
                        else
                        {
                                next[i] = next[j];
                        }
                }
                else
                {
                        j = next[j];
                }
        }
}

接下来，在函数Index_KMP()中，你需要对pos的取值进行判断，保证在合法范围内。修改代码如下：

int Index_KMP( Str *S, Str *T, int pos )
{
        if (pos < 1 || pos > S->cap) {
                return 0; // pos超出范围，直接返回0
        }
        
        int i = pos;
        int j = 1;
        int next[T->cap];
        
        get_next( T, next );
        
        while( i <= S->cap && j <= T->cap)  // 小于等于号
        {
                if( j == 0 || S->str[i-1] == T->str[j-1] ) // 修改为str[i-1]和str[j-1]
                {
                        i++;
                        j++;
                }
                else
                {
                        j = next[j];
                }
        }
        
        if( j > T->cap )
        {
                return i - T->cap;
        }
        else
        {
                return 0;
        }
}

最后，在函数CreateStr()中，你没有为字符数组分配内存空间。修改代码如下：

void CreateStr(Str **S)
{
        *S = (Str *)malloc(sizeof (Str));
        if (!(*S))
        {
                perror("INIT:malloc");
                exit(EXIT_FAILURE);
        }

        printf("请输入一个字符串，输入回车结束：");

        int size = 10; // 假定初始容量为10
        int length = 0; // 用于记录字符串的长度
        char ch;

        (*S)->str = (char *)malloc(sizeof(char) * size); // 分配初始内存空间

        if (!((*S)->str))
        {
                perror("INIT:malloc");
                exit(EXIT_FAILURE);
        }

        while ((ch = getchar()) != '\n')
        {
                (*S)->str[length] = ch; 
                length++; 

                if (length == size) // 当存储空间不够时，动态扩展内存
                {
                        size *= 2;
                        (*S)->str = (char *)realloc((*S)->str, sizeof(char) * size);
                        
                        if (!((*S)->str))
                        {
                                perror("INIT:realloc");
                                exit(EXIT_FAILURE);
                        }
                }
        }

        (*S)->cap = length; // 字符串的长度就是数组的大小
}

现在，你可以重新运行程序测试KMP算法了。记得在程序结束前，释放动态分配的内存空间，避免内存泄漏。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

kerln888

学习了

芜湖666

sdf