//编制一个程序，分别采用B-F算法和KMP算法实现串的模式匹配。

#include <iostream>
using namespace std;

#define MaxSize 100

typedef struct sqstring
{
    char data[MaxSize];
    int length;
}SqString;

//创建串
void StrAssign(SqString &s, char cstr[])
{
    int i;
    for(i = 0; cstr[i]!='\0'; i++)
        s.data[i] = cstr[i];
    s.length = i;
}

//输出串
void DispString(SqString s)
{
    int i;
    if(s.length > 0)
        for(i = 0; i < s.length; i++)
        {
            cout<<s.data[i];
        }
        cout<<endl;
}

int index(SqString s, 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 0;
}

void GetNext(SqString t, int next[])
{
    int j, k, i;
    j = 0; k = -1; next[0] = -1;
    while(j < t.length - 1)
    {
        if(k==-1||t.data[j] == t.data[k])
        {
            j++;
            k++;
            next[j] = k;
            
        }
        else
            k = next[k];
    }
    for(i = 0; i < t.length; i++)
    {
        cout<<next[i]<<"   ";
    }
}

int KMPIndex(SqString s, SqString t)
{
    int next[MaxSize], i = 0, j = 0;
    GetNext(t, 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 0;
}

void main()
{
    SqString t, p;
    int i, next[100];

    StrAssign(t, "abcaabcbcabcacacb");
    cout<<"串t为:"<<endl;

    DispString(t);
   
    StrAssign(p, "bcbcabc");
    cout<<"串p为: "<<endl;;

    DispString(p);
    cout<<"B-F算法模式匹配结果, p在t中的位置为:"<<index(t, p)<<endl;
    cout<<"执行KMP算法"<<endl;
    cout<<"j      ";
    for(i = 0; i < p.length; i++)
    {
        cout<<p.data[i]<<"   ";
    }
    cout<<endl;
    cout<<"next  ";
    GetNext(p, next);
    cout<<endl;
    cout<<"KMP算法模式匹配结果, p在t中的位置为:"<<KMPIndex(t, p)<<endl;
}