#include"stdio.h"
#include"string.h"
#define M 100
#define N 25
#define L 24
int flink[N];/*存储失败连接值*/
int d[L];/*存储函数d(x)的值*/

int menuSelect()/*菜单函数*/
{
    int x;
    printf("~~~~~~~~~模式匹配~~~~~~~~~~~\n");
    printf("    0.退出                     \n");
    printf("    1.简单模式匹配             \n");
    printf("    2.KMP模式匹配            \n");
    printf("    3.BM模式匹配             \n");
    printf("请选择方法：");
    scanf("%d",&x);
    return(x);
}

int strlength(char s[])/*计算串长函数*/
{
    int i;
    for(i=0;s[i]!='\0';i++);
        return(i);
}

void simple_match(char t[],char p[])/*简单的模式匹配函数*/
{
    int i,j,l,m,x;
    int k=0;
    l=strlength(t);
    m=strlength(p);
    for(i=0;i<=l-m;i++)
    {
        for(j=0,x=i;j<m&&t[x]==p[j];x++,j++)
            if(j+1==m) k=1;
            
        if(k==1) break;
    }
   
    if(k==1)
        printf("匹配成功，位置位于第%d个字符\n",i+1);
    else
        printf("匹配失败\n");
        
    printf("fanhui\n");
    getch();
}

void faillink(char p[])/*求失败连接值的函数*/
{
    int j=1;
    int k,i,x;
    x=strlength(p);
    flink[0]=-1;
    while(j<x)
    {
        k=flink[j-1];
        
        while(k!=-1&&p[k]!=p[j-1])
            k=flink[k];
            
        flink[j]=k+1;
        j++;
    }
}

void kmp_match(char t[],char p[])/*KMP模式匹配算法函数*/
{
    int i,j,l,m,k;
    l=strlength(t);
    m=strlength(p);
    i=0;
    j=0;
    k=0;
    faillink(p);
    while(i<l)
    {
        while(j!=-1&&p[j]!=t[i])
        j=flink[j];
        if(j==m-1)
        {
            k=1;
            break;
        }
        i++;j++;
    }
   
    if(k==1)
        printf("匹配成功，位置位于第%d个字符\n",i-m+2);
    else
        printf("匹配失败\n");
        
    printf("fanhui\n");
    getch();
}

void dx(char p[])/*求d(x)函数*/
{
    int i,m;
    m=strlength(p);
   
    for(i=0;i<L;i++)
        d[i]=m;
        
    for(i=0;i<m-1;i++)  
        d[p[i]-'a']=m-i-1;
}

void bm_match(char t[],char p[])/*求BM模式匹配函数*/
{
    int i,j,k,l,m,x=0;
    l=strlength(t);
    m=strlength(p);
    dx(p);
    i=m-1;
    do
    {
        j=m-1;
        k=i;
        while(j>=0&&p[j]==t[k])
        {
            j--;
            k--;
        }
        
        if(j<0)
        {
            x=1;
            break;
        }
        i+=d[t[i]-'a'];
    }while(i<l);
   
    if(x==1) printf("匹配成功，位置位于第%d个字符\n"，i-m+2);
    else printf("匹配失败\n");   
}
main()
{
    char T[M],P[N];
    int i;
    printf("请输入主串和模式串\n");
    gets(T);gets(P);
    for(i=1;i!=0;)
    {
        i=menuSelect();
        switch(i)
        {
            case 0:;break;
            case 1:simple_match(T,P);break;/*进行简单的模式匹配*/
            case 2:kmp_match(T,P);break;/*进行KMP模式匹配*/
            case 3:bm_match(T,P);break;/*进行BM模式匹配*/
        }
    }
}