Bruce-Force算法与KMP算法匹配【C语言】

题目:

__令主串为aaabbbababaabb，子串为abaa，试分别用Bruce-Force算法和KMP算法给出其匹配过程。
__

时间复杂度不唯一	空间复杂度不唯一

代码:

/*3-4*/
#include <stdio.h>
#include <stdlib.h>
#define size 100
typedef struct
{
    char ch[size];
    int len;
}Seqstring;
void Create(Seqstring *S)
{
    int i;
    for(i=0;i<S->len;i++)
    {
        scanf(" %c",&S->ch[i]);
    }
}
void BF(Seqstring *S,Seqstring *T)
{
    int i=0;
    int j=0;
    while(i<=S->len-1 && j<=T->len-1)
    {
        if(S->ch[i]==T->ch[j])
        {
            ++i;
            ++j;
        }
        else
        {
            i=i-j+1;
            j=0;
        }
        if(j>=T->len)
        {
            printf("匹配成功...\n匹配位置为:\n");
            printf("%d\n",i+1-T->len);
            return;
        }
    }
    printf("匹配失败...\n");
}
void kmp_next(Seqstring *T,int *next)
{
    int i=1;
    int j=0;
    next[1]=0;
    while(i<T->len)
    {
        if(j==0 || T->ch[i-1]==T->ch[j-1])
        {
            ++i;
            ++j;
            next[i]=j;
        }
        else
        {
            j=next[j];
        }
    }
}
void view_next(Seqstring *S,int *next)
{
    int i;
    for(i=1;i<=S->len;i++)
    {
        printf("%d ",next[i]);
    }
    printf("\n");
}
void kmp(Seqstring *S,Seqstring *T)
{
    int i=1;
    int j=1;
    int next[size];
    kmp_next(T,next);
    while(i<=S->len && j<=T->len)
    {
        if(j==0 || S->ch[i-1]==T->ch[j-1])
        {
            ++i;
            ++j;
        }
        else
        {
            j=next[j];
        }
    }
    if(j>=T->len)
    {
        printf("匹配成功...\n匹配位置为:\n");
        printf("%d\n",i-T->len);
    }
    else
    {
        printf("匹配失败...\n");
    }
}
int main()
{
    Seqstring s1;
    s1.len=14;
    printf("请您输入--主串:\n");
    Create(&s1);
    Seqstring s2;
    s2.len=4;
    printf("请您输入--子串:\n");
    Create(&s2);
    printf("Bruce-Force算法匹配:\n");
    BF(&s1,&s2);
    printf("KMP算法匹配:\n");
    int next[size];
    kmp_next(&s2,next);
    printf("显示next数组:\n");
    view_next(&s2,next);
    kmp(&s1,&s2);
    printf("hello world!\n");
    return 0;
}

---

运行情况:

请您输入--主串:
aaabbbababaabb
请您输入--子串:
abaa
Bruce-Force算法匹配:
匹配成功...
匹配位置为:
9
KMP算法匹配:
显示next数组:
0 1 1 2 
匹配成功...
匹配位置为:
9
hello world!
Program ended with exit code: 0

Copyright © 2019 wyq. All rights reserved.