KMP算法

//求next 列表
int * StringNext(string p)
{
    int *next=new int[p.length()];
    int k=-1;
    int j=0;
    next[0]=-1;
    while(j<p.length()-1)
    {
        if(k==-1||p[j]==p[k])
            next[++j]=++k;
        else
            k=next[k];
    }
    return next;
}

int FindString(string T, string p)
{
    int * next=StringNext(p);
    int i=0, j=0;
    while(i<T.length()&&j<p.length())
    {
        if(T[i]==p[j])
        {
            i++;
            j++;
            continue;
        }
        if(j==0) // j为初始位置，移动i
            i++;
        else //否则移动j
            j=next[j];
        
    }
    if (j==p.length())
        return i-j;
    else
        return -1;
}

string a1="abcabaaaabaabcac";
string a2="abaabcac";

int rlt = FindString(a1, a2);
// 结果为8

//KMP算法，加了可视化匹配过程
int FindString(string T, string p)
{
    int * next=StringNext(p);
    int i=0;
    int j=0;
    int k=0;
    cout<<T.length()<<"::::"<<p.length()<<endl;
    while(i<T.length()&&j<p.length())
    {
        cout<<"T["<<j<<"]"<<"<->"<<"p["<<i<<"]"<<endl;
        for(k=0;k<T.length();k++)
        {
            if(k==i)
            {
                cout<<"<"<<T[k]<<">";
            }
            else
                cout<<T[k];
        }
        cout<<endl;
        for(k=0;k<i-j;k++)cout<<" ";
        for(k=0;k<p.length();k++)
        {
            if(k==j)
            {
                cout<<"<"<<p[k]<<">";
            }
            else
                cout<<p[k];
        }
        cout<<endl;
        cout<<endl;
        if(T[i]==p[j])
        {
            i++;
            j++;
            continue;
        }
        if(j==0) // j为初始位置，移动i
            i++;
        else //否则移动j
            j=next[j];
        
    }
    cout<<j<<"<->"<<i<<endl;
    if (j==p.length())
        return i-j;
    else
        return -1;
}

匹配过程

16::::8
T[0]<->p[0]
<a>bcabaaaabaabcac
<a>baabcac

T[1]<->p[1]
a<b>cabaaaabaabcac
a<b>aabcac

T[2]<->p[2]
ab<c>abaaaabaabcac
ab<a>abcac

T[0]<->p[2]
ab<c>abaaaabaabcac
  <a>baabcac

T[0]<->p[3]
abc<a>baaaabaabcac
   <a>baabcac

T[1]<->p[4]
abca<b>aaaabaabcac
   a<b>aabcac

T[2]<->p[5]
abcab<a>aaabaabcac
   ab<a>abcac

T[3]<->p[6]
abcaba<a>aabaabcac
   aba<a>bcac

T[4]<->p[7]
abcabaa<a>abaabcac
   abaa<b>cac

T[1]<->p[7]
abcabaa<a>abaabcac
      a<b>aabcac

T[0]<->p[7]
abcabaa<a>abaabcac
       <a>baabcac

T[1]<->p[8]
abcabaaa<a>baabcac
       a<b>aabcac

T[0]<->p[8]
abcabaaa<a>baabcac
        <a>baabcac

T[1]<->p[9]
abcabaaaa<b>aabcac
        a<b>aabcac

T[2]<->p[10]
abcabaaaab<a>abcac
        ab<a>abcac

T[3]<->p[11]
abcabaaaaba<a>bcac
        aba<a>bcac

T[4]<->p[12]
abcabaaaabaa<b>cac
        abaa<b>cac

T[5]<->p[13]
abcabaaaabaab<c>ac
        abaab<c>ac

T[6]<->p[14]
abcabaaaabaabc<a>c
        abaabc<a>c

T[7]<->p[15]
abcabaaaabaabca<c>
        abaabca<c>

8<->16