数据结构 字串的模式匹配 KMP算法
【摘要】 #include <stdio.h>#include <stdlib.h> #define OK 1#define ERROR 0#define OVERFLOW -2 typedef struct{ char *ch; int length;}String; void Init_String(String &T){ T.ch = NULL; ...
-
#include <stdio.h>
-
#include <stdlib.h>
-
-
#define OK 1
-
#define ERROR 0
-
#define OVERFLOW -2
-
-
typedef struct
-
{
-
char *ch;
-
int length;
-
}String;
-
-
void Init_String(String &T)
-
{
-
T.ch = NULL;
-
T.length = 0;
-
}
-
-
int StrAssign(String &T, char *chars)
-
{
-
int i;
-
int len;
-
char *p = chars;
-
if (T.ch)
-
{
-
free(T.ch);
-
}
-
for (len = 0;*p != '\0'; ++len,++p);
-
if (!len)
-
{
-
T.ch = NULL;
-
T.length = 0;
-
}
-
else
-
{
-
T.ch = (char *)malloc(len * sizeof(char));
-
if (!T.ch)
-
{
-
exit(OVERFLOW);
-
}
-
for (i=0; i<len; i++)
-
{
-
T.ch[i] = chars[i];
-
}
-
T.length = len;
-
}
-
return OK;
-
}
-
-
-
-
void get_next(String T, int next[])
-
{
-
int i = 0;
-
int j = -1;
-
next[0] = -1;
-
while (i<T.length)
-
{
-
if (j == -1 || T.ch[i] == T.ch[j])
-
{
-
++i;
-
++j;
-
next[i] = j;
-
}
-
else
-
{
-
j = next[j];
-
}
-
}
-
}
-
-
-
int Index_KMP(String S, String T, int pos)
-
{
-
int i = pos;
-
int j = -1;
-
int next[255];
-
get_next(T,next);
-
while (i<S.length && j <T.length )
-
{
-
if (j == -1 || S.ch[i] == T.ch[j])
-
{
-
++i;
-
++j;
-
}
-
else
-
{
-
j = next[j];
-
}
-
}
-
if (j == T.length )
-
{
-
return i-T.length + 1 ;
-
}
-
else
-
return 0;
-
}
-
-
-
-
-
int main()
-
{
-
String S,T;
-
Init_String(S);
-
Init_String(T);
-
StrAssign(S,"abcdefghijklmm");
-
StrAssign(T,"cdef");
-
printf("%d\n",Index_KMP(S,T,0));
-
return 0;
-
}
文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/qq523176585/article/details/17249191
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）