这段代码实现了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 小助理,如未能正确解答您的问题,请继续追问。 |