KMP算法c实现
需积分: 10 138 浏览量
2015-02-14
16:50:20
上传
评论 1
收藏 15KB DOCX 举报
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void kmp_init(const char *patn, int len, int *next)
{
int i, j;
"
if(NULL==patn || len<0 || NULL==next)
return;
next[0] = 0;
for (i = 1, j = 0; i < len; i ++) {
while (j > 0 && patn[j] != patn[i])
j = next[j - 1];
if (patn[j] == patn[i])
j ++;
next[i] = j;
}
}
"
int kmp_3nd(const char *text, int text_len, const char *patn,
int patn_len, int *next)
{
int i, j;
"
if(NULL==text || text_len<=0 || NULL==patn || patn_len<=0 ||
NULL==next)
return -1;
for (i = 0, j = 0; i < text_len; i ++ ) {
while (j > 0 && text[i] != patn[j])
j = next[j - 1];
if (text[i] == patn[j])
j ++;
if (j == patn_len)
return i + 1 - patn_len;
}
return -1;
}
"
int kmp_match(const char *text, int text_len, const char *patn, int patn_len)
{
int i, pos;
int *next;
next = calloc(patn_len, sizeof(int));
kmp_init(patn, patn_len, next);
资源评论
