字符串匹配——KMP算法

#include<iostream>
#include<string>
using namespace std;

int* Next;

int KMP(char* Str, char* SubStr);
void NextTable(char* Str);

int main(void)
{
    string A, B;
    cin >> A;
    cin >> B;

    char* Str=const_cast<char*>(A.c_str());
    char* SubStr=const_cast<char*>(B.c_str());

    //cout << Str << endl << SubStr << endl;

    Next = new int[strlen(Str)];

    NextTable(Str);
    cout << KMP(Str, SubStr) << endl;

    system("pause");
    return 0;
}

int KMP(char* Str, char* SubStr)
{
    int i = 0;
    int j = 0;

    while (i < strlen(Str) && j < strlen(SubStr))
    {
        if (j == -1 || Str[i] == SubStr[j])
        {
            i++;
            j++;
        }
        else
            j = Next[j];
    }

    if (j == strlen(SubStr))
        return i - j;
    else
        return -1;
}

void NextTable(char* Str)
{
    int i = 0, j = -1;
    Next[0] = -1;

    while (i < strlen(Str))
    {
        if (j == -1 || Str[i] == Str[j])
        {
            ++i;
            ++j;
            Next[i] = j;
        }
        else
            j = Next[j];
    }
}