《数据结构和算法》——KMP算法实现

luciferzf

利用一个next数组存储匹配串每一个位置的回溯下标，当用匹配串与被匹配串进行逐个比较时，若出现匹配错误，可以利用next数组快速回溯。
next数组：当前缀和后缀一致时，记录一次下标；若不一致，固定后缀，回溯前缀直至最开始的下标0，记录下标1，表示需要从头开始匹配。利用next数组我们可以快速地根据匹配串中重复的部分减少匹配次数。

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

void GetNext(char T[], int next[])
{
        int i=1, j=0;
        next[1] = 0;
        while (i < T[0])
        {
                if (0 == j || T[i] == T[j])
                {
                        i++;
                        j++;
                        if (T[i] == T[j])
                        {
                                next[i] = next[j];
                        }
                        else
                        {
                                next[i] = j;
                        }
                }
                else
                {
                        j = next[j];
                }

        }
}

void GetString(char str[])
{
        int i;
        char temp;
        scanf_s("%c", &temp);
        for (i = 1; temp != ' '&&temp != '\n'; i++)
        {
                str[i] = temp;
                scanf_s("%c", &temp);
        }
        str[0] = i - 1 ;
}

int KMP(char S[], char T[],int next[])
{
        int i=1,j=1;
        int flag = 0;
        while (i <= S[0] )
        {
                if (j==0||S[i] == T[j])
                {
                        i++;
                        j++;
                }
                else
                {
                        j = next[j];
                }
                if (j > T[0] )
                {
                        flag = 1;
                        break;
                }
        }
        if (flag)return i;
        else return 0;
}


int main()
{
        char S[256], T[256] ;
        int next[256];

        cout << "输入主串:";
        GetString(S);
        cout << "输入子串:";
        GetString(T);

        GetNext(T, next);

        int pos = KMP(S, T, next)-T[0];

        if (pos)cout << "YES,in the no." << pos << endl;
        else cout << "NO"<< endl;

        system("PAUSE");
}