KMP模式匹配算法實現與改進

/KMP模式匹配算法實現/
//通過計算返回子串T的next數組
void get_next(String T,int * next)
{
    int i,j;
    i = 1;
    j = 0;
    next[1] = 0;
    while (i < T[o]) //T[0]表示串T的長度
    {
        if (j == 0 || T[i] == T[j]) //T[i]表后綴的單個字符，T[j]表前綴的單個字符
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];    //若字符不相同，則j值回溯
    }
}

//返回子串T在主串S中的pos個字符之后的位置。若不存在返回值0
int Index_KMP(String S,String T,int pos)
{
    int i = pos;
    int j = 1;
    int next[255];  //定義一個next數組
    get_next(T,next);   //對串T作分析，得到next數組
    while (i <= S[0] && j<= T[0]) //S[0]和T[0]為主串個子串的長度
    {
        if (j == 0 || S[i] == T[j])
        {
            ++i;
            ++j;

        }
        else
        {
            j = next[j];    //j退回合適的位置，i值不變
        }
    }
    if (j > T[0])
        return i-T[0];
    else
        return 0;
}</pre>
/*KMP模式匹配算法的改進*/
//通過計算返回子串T的nextval數組
void get_nextval(String T,int * nextval)
{
    int i,j;
    i = 1;
    j = 0;
    nextval[1] = 0;
    while (i < T[0]) //T[0]表示串T的長度
    {
        if (j == 0 || T[i] == T[j]) //T[i]表后綴的單個字符，T[j]表前綴的單個字符
        {
            ++i;
            ++j;
            if (T[i] != T[j])   //若當前字符與前綴字符不同
                nextval[i] = j; //則當前的j為nextval在i位置的值
            else
                nextval[i] = nextval[j];    //如果字符相同，則將前綴字符的nextval值賦給nextval在i位置的值
        }
        else
            j = nextval[j]; //若字符不相同，則j值回溯
    }
}
轉自：http://blog.csdn.net/hacke2/article/details/7295628&nbsp;