kmp算法代码示例

//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