KMP算法 KMP算法

#include<iostream>
#include <cstring>
#include<cstdlib>

using namespace std;

int BF(char s[], char t[])            //BF算法
{
    int i = 0, j = 0;
    int m = strlen(s);
    int n = strlen(t);
    while (i < m&&j < n)
    {
        if (s[i] == t[j])
        {
            i++; j++;
        }
        else
        {
            i = i - j + 1; j = 0;
        }
    }
    if (j >= n)
        return i - n + 1;
    else
        return -1;
}

void GetNext_one(char t[], int next[])  //下标为 1 开始 
{

    int j = 1, k = 0;
    int n = strlen(t);
    next[j] = 0;
    while (j < n)
    {
        if (k == 0 || t[j] == t[k])
        {
            j++; k++; next[j] = k;
        } 
        else
        {
            k = next[k];
        }
    }
}

void GetNext_two(char t[], int next[])    //下标为0 
{

    int j = 0, k = -1;
    int n = strlen(t);

    next[j] = -1;
    while (j < n)
    {
        if (k == -1 || t[j] == t[k])
        {
            j++; k++; next[j] = k;
        }
        else
        {
            k = next[k];
        }
    }
}

int IndexKMP_one(char s[], char t[], int next[], int pos)
{
    int i, j;
    i = pos - 1; j = 0;
    int m = strlen(s),n = strlen(t);
    while (i<m && j<n)
        if (j == 0 || s[i] == t[j])
        {
            i++; j++;
        }// 继续比较后继字符
        else j = next[j];// 模式串向右移动
    if (j >= n) return i - n + 1; // 匹配成功
    return -1;
}

int IndexKMP_two(char s[], char t[], int next[], int pos)
{
    int i, j;
    i = pos - 1; j = 0;
    int m = strlen(s),n = strlen(t);
    while (i<m && j<n)
        if (j == -1 || s[i] == t[j])
        {
        i++; j++;
        }// 继续比较后继字符
        else j = next[j];// 模式串向右移动
        if (j >= n) return i - n + 1; // 匹配成功
        return -1;
}

int main()
{
    //char s[] = "aaabaaaabaa", t[] = "aaaab";
    char *s = "ababaaabaabcabcacabbaaababcd", *t = "abcabcacab"; //char *s = "aaaaaaabaa", *t = "abcdsb";ababaaababaa 
    int i = BF(s, t);              //abcabcacab
    cout << i << endl;
    int n = strlen(t);
    int *next, x = 0;
    next = new int[n+1];
    //next = (int *)malloc(sizeof(int)*n);
    
    GetNext_one(t, next);                 // next从 0开始 ( 1---n )

//    next[1] = 0; next[2] = 1; next[3] = 1; next[4] = 1; next[5] = 2; next[6] = 3; next[7] = 4;next[8] = 5; next[9] = 1;
//    next[10] = 2;
    for (int i = 1; i <= n; i++)
        cout << next[i] << ' ';
    cout << endl;
    
    x = IndexKMP_one(s, t, next, 1);          

    cout << x << endl;
    
    cout << "=================== 2 =====================n";

    GetNext_two(t, next);
    for (int i = 0; i < n; i++)          //next从 -1 开始 （0 ~ n-1) 
        cout << next[i] << ' ';
    
    cout << endl;
    x = IndexKMP_two(s, t, next, 1);

    cout << x << endl;

    system("pause");
    return 0;
}