KMP算法

设目标字符串S，起配位置为j；模式字符串T，起配位置为i。

暴力匹配：每次失配后，从j+1位置重新开始和T匹配。

伪代码：

def index_BF(T, S, pos):
    while pos+len(T)<=len(S):
        j=pos
        for i in range(len(T)):
            if S[j]==T[i]:
                j+=1
                i+=1
            else:
                pos+=1
                break
        else:
            return pos
    return -1

T='girl'
S='i love the girl'
print index_BF(T,S,0)

KMP算法：核心--构造next数组记录模式字符串每个位置失配时应该回溯到的位置。

#include<iostream>
using namespace std;

void getNext(const char* T, int* next)
{
    next[1]=0; //第一个位置失配后，与T[0]对齐
    int i=1; //变化后缀i,前缀固定1开始
    int j=0; 
    while(i<T[0])//后缀到倒数第二个，也就是T最后一个位置失配
    {
        if(0==j || T[i]==T[j]) //依次往后走
        {
            i++;
            j++;
            if(T[i]!=T[j])
            {
                next[i]=j;
            }
            else    // 连续两个位置相等,直接回溯的源头
                next[i]=next[j];
        }
        else
        {
            j=next[j];  //模式串T失配，前缀j回溯
        }
    }
}

int index_KMP(char* S,char* T,int pos)
{
    int i=pos;
    int j=1;
    int next[255];
    getNext(T,next);
    while(i<=S[0] && j<=T[0])
    {
        if(j==0 || S[i]==T[j])
        {
            i++;
            j++;
        }
        else
        {
            j=next[j];//失配后对齐位置,有可能跳到j=0
        }
    }
    if(j>T[0]) //成功匹配
    {
        return i-T[0];
    }
    else
        return -1;

}

int get_len(const char *str)
{
    int i=0;
    while(str[i]!='')i++;
    return i;
}

int main()
{
    char T[255]=" abbaa";
    T[0]=get_len(T)-1;
    char S[255]=" xfsnbabaabbaaaaaabb";
    S[0]=get_len(S)-1;
    cout<<index_KMP(S,T,1)<<endl;;
    return 0;
}