View Code
int next[20] ={0};
//注意返回結果是一個數組next，保存m個k值得地方，即若next[j]=k
//則str[0]str[1]…str[k] = str[j-k]str[j-k+1]…str[j]
//這樣當des[t+j+1]和pat[j+1]匹配失敗時，下一個匹配位置為des[t+j+1]和next[j]+1
void Next(char str[],int len)
{
    next[0] = -1;
    for(int j = 1 ; j < len ; j++)
    {
        int i = next[j-1];
        while(str[j] != str[i+1] && i >= 0)//迭代的過程
        {
            i = next[i];
        }
        if(str[j] == str[i+1])
        {
            next[j] = i+1;
        }
        else
        {
            next[j] = -1;
        }
    }
}

View Code
//des是目標串，pat是模式串，len1和len2是串的長度
int kmp(char des[],int len1,char pat[],int len2)
{
    Next(str2,len2);
    int p=0,s=0;
    while(p < len2  && s < len1)
    {
        if(pat[p] == des[s])
        {
            p++;s++;
        }
        else
        {
            if(p==0)
            {
                s++;//若第一個字符就匹配失敗，則從des的下一個字符開始
            }
            else
            {
                p = next[p-1]+1;//用失敗函數確定pat應回溯到的字符
            }
        }
    }
    if(p < len2)//整個過程匹配失敗
    {
        return -1;
    }
    return s-len2;
}