/*
*
* KMP算法
* 算法思想详见数据结构,查找子串一节
*
*/
#include <stdio.h>
#define MAXSIZE 128 /*定义next数组长度*/
int find_sub_string(const char *str, const char *substr);
int main(void)
{
char *str = "hello world";
char *sub_str = "llo";
int result = 0;
result = find_sub_string(str, sub_str);
printf("%d\n", result);
printf("Please input any key to exit...");
getch();
return 0;
}
int find_sub_string(const char *str, const char *substr)
{
int i = 0;
int j = 0;
int next[MAXSIZE] = {0};
next[0] = 0;
next[1] = 0;
i = 1;
while (i < strlen(substr)-1) /*由子串确定next数组中的元素*/
{
if (substr[i] == substr[j])
{
i++;
j++;
next[i] = j;
}
else if (0 == j)
{
i++;
next[i] = j;
}
else
{
j = next[j];
}
}
i = 0;
j = 0;
while ((i < strlen(str)) && (j < strlen(substr))) /*查找子串的位置*/
{
if (str[i] == substr[j])
{
i++;
j++;
}
else if (0 == j)
{
i++;
}
else
{
j = next[j];
}
}
if (j >= strlen(substr))
{
return (i-j);
}
else
{
return -1;
}
}
追问getch strlen 没有定义
追答getch() 删除了
加上头文件#include
本回答被提问者采纳