KMP C++

KMP C++实现

int * ComputeNext(string P)
{
    int *lsp{ new int[P.length()] };

    lsp[0] = 0;  // Base case
    int j = 0;

    for (int i = 1; i < P.length(); i++)
    {//        int j = lsp[i - 1];
        while (j > 0 && P.at(i) != P.at(j))
            j = lsp[j];

        if (P.at(i) == P.at(j))
            j++;

        lsp[i] = j;
    }
    return lsp;
}

int search(string P, string T)
{
    int *lsp= ComputeNext(P);

    for (int var = 0; var < P.length(); var++)
    {
        cout << *(lsp+var) << " ";
    }
    cout<<endl;
    int j = 0;                                

    for (int i = 0; i < T.length(); i++)
    {
        while (j > 0 && T.at(i)!= P.at(j))
        {                                    
            j = *(lsp+j);                    
            cout<<"-i:"<<j<<endl;
        }
        cout<<i<<" "<<T.at(i)<<","<<j<<" "<<P.at(j)<<"|| ";
        if (T.at(i) == P.at(j))
        {
            j++;

            if (j == P.length())
                return (i -P.length()+1) ;

            cout<<T.at(i)<<","<<P.at(j)<<":";
        }

        cout<<i<<"-"<<j<<endl;

    }
    delete []lsp;
    return -1;        
}