KMP算法的实现
#include <stdio.h>#include <stdlib.h>
//给char * 起名为String
typedef char* String;
//定义一个结构体，str存储字符串，cap存储字符串的长度
typedef struct
{
char str;
int cap;
}Str;
//获取next数组，这个是KMP算法的灵魂
void get_next(Str *T, int *next )
{
int j = 0;
int i = 1;
next = 0;
while( i < T->str ) //当循环次数超过字符串的长度的时候退出循环
{
if( 0 == j || T->str == T->str )
{
i++;
j++;
if( T->str != T->str ) //改进后的算法
{
next = j;
}
else
{
next = next;
}
}
else
{
j = next;
}
}
}
// 返回子串T在主串S第pos个字符之后的位置
// 若不存在，则返回0
int Index_KMP( Str *S, Str *T, int pos )
{
int i = pos;
int j = 1;
int next;
get_next( T, next );
while( i <= S->cap && j <= T->cap)
{
//增加判断，防止特殊情况发生
if( 0 == j || S->str == T->str )
{
i++;
j++;
}
else
{
j = next;
}
}
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 = 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("否");
}
这段代码实现了KMP算法，用来查找子串在主串中的位置。不过代码中有一些错误和不完善的地方，我来帮你解决。
首先，在函数get_next()中，你需要将next定义为数组，而不是整数。next数组存储的是匹配失败时下一次比较的位置，所以它的长度应该与字符串T的长度相同。修改代码如下：
void get_next(Str *T, int *next )
{
int j = 0;
int i = 1;
next = 0; // 初始化next为0
while( i < T->cap ) //修改为cap
{
if( 0 == j || T->str == T->str ) // 修改为str和str
{
i++;
j++;
if( T->str != T->str ) //改进后的算法
{
next = j;
}
else
{
next = next;
}
}
else
{
j = next;
}
}
}
接下来，在函数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;
get_next( T, next );
while( i <= S->cap && j <= T->cap)// 小于等于号
{
if( j == 0 || S->str == T->str ) // 修改为str和str
{
i++;
j++;
}
else
{
j = next;
}
}
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 = 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 小助理，如未能正确解答您的问题，请继续追问。 学习了 sdf
页:
[1]
2