//kmp_algorithm.c
#include "kmp_algorithm.h"
// ?ónextoˉêy?μ
void get_next(char T[], int strLen, int next[])
{
int i = 1, j = 0;
next[1] = 0;
j = 0;
while(i <= strLen)
{
if(0 == j || T[i] == T[j])
{
++i;
++j;
next[i] = j;
}
else
{
j = next[j];
}
}
}
/*
à?ó??￡ê?′?Tμ?nextoˉêy?óT?ú?÷′?S?Dμúpos??×?·???oóμ?????μ?KMP??·¨
D￡?1 <= pos <= strlen(S)
*/
// ·μ??T?úS?Dμ??eê?????
int KMP_algorithm(char S[], int S_len, char T[], int T_len, int pos)
{
int i = pos;
int j = 1;
int next[MAX_NEXT];
get_next(T, T_len, next);
while(i < S_len && j < T_len)
{
if(0 == j || S[i] == T[j])
{
++i;
++j;
}
else
{
j = next[j];
}
}
return (i - j);
}
========================================================================
// kmp_algorithm.h
#ifndef _KMP_ALGORITHM_H_
#define _KMP_ALGORITHM_H_
#include <stdio.h>
#define MAX_NEXT 1024*1024
/*
′?μ??￡ê??￥??￡??óμúò???×?·?′??úμú?t??×?·?′??Dμ?????
*/
int KMP_algorithm(char S[], int S_len, char T[], int T_len, int pos);
#endif
本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请
点击举报。
