【算法】KMP算法實作順序串各種模式比對運算的算法設計

【C++版】  

 

一、設計任務：

編寫程式，利用順序串的基本運算，建立目标串以及模式串，用BF算法求出t在s中的位置，求出模式串的next數組以及nextval數組。KMP算法使用next數組以及改進的KMP算法使用nextval數組求出t在s中的位置，并給出經過各種模式比對算法的結果。

 

二、源代碼：

頭檔案：

#define MaxSize 100  //指定串的最大長度
class PatternMatching {  //模式比對
public:
    typedef struct
    {
        char data[MaxSize];  //串字元
        int length;  //串長
    } SqString;  // 聲明順序串類型
	
	//靜态方法
    static void StrAssign(SqString &s, const char cStr[]);  //生成串
    static void DestroyStr(SqString &s);  //銷毀串
    static void DispStr(SqString s );  //輸出串
    static int BF(SqString s,SqString t);  //BF算法
    static void GetNext(SqString t,int next[]);  //求next數組
    static int KMPIndex(SqString s,SqString t);  //KMP算法
    static void GetNextVal(SqString t,int nextVal[]);  //求nextVal數組
    static int KMPIndexImprove(SqString s,SqString t);  //改進後的KMP算法

};
           

源檔案：

#include "PatternMatching.h"
#include <iostream>
using namespace std;

int main()
{
    PatternMatching::SqString s, t;  //聲明目标串s和模式串t
    int next[MaxSize];
    int nextVal[MaxSize];

    PatternMatching::StrAssign(s, (char *) "abcabcdabcdeabcdefabcdefg");  //生成串
    PatternMatching::StrAssign(t, (char *) "cdefabcde");
    cout << "目标串s:";
    PatternMatching::DispStr(s);  //輸出目标串
    cout << "模式串t:";
    PatternMatching::DispStr(t);  //輸出模式串
    cout << "\n-------測試BF算法------\n";
    cout << "模式串t在目标串s中的位置是：" ;
    cout << PatternMatching::BF(s, t) << endl;  //傳回位置
    cout << "\n-------測試KMP算法------\n";
    PatternMatching::GetNext(t,next);  //求模式串的next數組
    cout<<"next數組：";
    for (int i=0;i<t.length;i++)
        cout<<next[i]<<" ";
    cout << "\n模式串t在目标串s中的位置是：" ;
    cout << PatternMatching::KMPIndex(s,t)<< endl;  //傳回位置
    cout << "\n-------測試改進後的KMP算法------";
    PatternMatching::GetNextVal(t,nextVal);  //求模式串的nextVal數組
    cout<<"\nnextVal數組：";
    for (int i=0;i<t.length;i++)
        cout<<nextVal[i]<<" ";
    cout << "\n模式串t在目标串s中的位置是：" ;
    cout << PatternMatching::KMPIndexImprove(s,t)<< endl;  //傳回位置
    PatternMatching::DestroyStr(s);  //銷毀串
    PatternMatching::DestroyStr(t);
    return 0;
}

/*-----------------BF算法-----------------*/
int PatternMatching::BF(PatternMatching::SqString s, PatternMatching::SqString t)
{
    int i = 0, j = 0;
    while (i < s.length && j < t.length)
    {
        if (s.data[i] == t.data[j])
        {
            i++;
            j++;
        } else
        {
            i = i - j + 1;
            j = 0;
        }
    }
    if (j >= t.length)
        return (i - t.length);
    else
        return (-1);
}

/*-----------------求next數組-----------------*/
void PatternMatching::GetNext(PatternMatching::SqString t, int next[])
{
    int j=0;  //j掃描t
    int k=-1;  //k記錄t[j]之前與t開頭相同的字元個數
    next[0] = -1;  //設定next[0]值
    while (j < t.length - 1)  //求t所有位置的next值
    {
        if (k == -1 || t.data[j] == t.data[k])
        {
            j++;
            k++;
            next[j] = k;
        }
        else
            k=next[k];
    }
}

/*-----------------KMP算法-----------------*/
int PatternMatching::KMPIndex(PatternMatching::SqString s, PatternMatching::SqString t)
{
    int next[MaxSize],i=0,j=0;
    GetNext(t,next);  //求next數組
    while (i<s.length&&j<t.length)
    {
        if (j == -1 || s.data[i] == t.data[j])
        {
            i++;
            j++;
        }
        else
            j = next[j];
    }
    if (j>=t.length)
        return (i-t.length);
    else
        return (-1);
}

/*-----------------求nextVal數組-----------------*/
void PatternMatching::GetNextVal(PatternMatching::SqString t, int nextVal[])
{
    int j=0,k=-1;
    nextVal[0]=-1;
    while (j<t.length)
    {
        if (k == -1 || t.data[j] == t.data[k])
        {
            j++;
            k++;
            if (t.data[j] != t.data[k])
                nextVal[j] = k;
            else
                nextVal[j] = nextVal[k];
        }
        else
            k=nextVal[k];
    }
}

/*-----------------改進後的KMP算法，求t在s中的位置-----------------*/
int PatternMatching::KMPIndexImprove(PatternMatching::SqString s, PatternMatching::SqString t)
{
    int nextVal[MaxSize],i=0,j=0;
    GetNextVal(t,nextVal);  //求nextVal數組
    while (i<s.length&&j<t.length)
    {
        if (j == -1 || s.data[i] == t.data[j])
        {
            i++;
            j++;
        }
        else
            j = nextVal[j];
    }
    if (j>=t.length)
        return (i-t.length);
    else
        return (-1);
}




/*-----------------生成串-----------------*/
void PatternMatching::StrAssign(SqString &s, const char cStr[])
{
    int i;
    for (i = 0; cStr[i] != '\0'; i++)
        s.data[i] = cStr[i];
    s.length = i;
}

/*-----------------銷毀串-----------------*/
void PatternMatching::DestroyStr(PatternMatching::SqString &s)
{
    cout<<"\n串銷毀成功！";
}

/*-----------------輸出串-----------------*/
void PatternMatching::DispStr(PatternMatching::SqString s)
{
    int i;
    if (s.length > 0)
    {
        for (i = 0; i < s.length; i++)
            cout << s.data[i];
        cout << endl;
    }
}
           

 

三、測試結果：