c說話中應用BF-KMP算法實例

c說話中應用BF-KMP算法實例。本站提示廣大學習愛好者：（c說話中應用BF-KMP算法實例）文章只能為提供參考，不一定能成為您想要的結果。以下是c說話中應用BF-KMP算法實例正文

直接上代碼


#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX_SIZE 255    //界說字符串的最年夜長度

typedef unsigned char SString[MAX_SIZE];//數組第一個保留長度
//BF
int BFMatch(char *s,char *p)
{
    int i,j;
    i=0;
    while(i < strlen(s))
    {
        j=0;
        while(s[i]==p[j]&&j < strlen(p))
        {
            i++;
            j++;
        }
        if(j==strlen(p))
            return i-strlen(p);
        i=i-j+1;                //指針i回溯
    }
    return -1;   
}
//getNetx
void getNext(char *p,int *next)
{
    int j,k;
    next[0]=-1;
    j=0;
    k=-1;
    while(j < strlen(p)-1)
    {
        if(k==-1||p[j]==p[k])    //婚配的情形下,p[j]==p[k]
        {
            j++;
            k++;
            next[j]=k;
        }
        else
        {                  //p[j]!=p[k]
            k=next[k];
        }
    }
}

//KMP
int KMPMatch(char *s,char *p)
{
    int next[100];
    int i,j;
    i=0;
    j=0;
    getNext(p,next);
    while(i < strlen(s))
    {
        if(j==-1||s[i]==p[j])
        {
            i++;
            j++;
        }
        else
        {
            j=next[j];       //清除了指針i的回溯
        }
        if(j==strlen(p))
        {
            return i-strlen(p);
        }
    }
    return -1;
}

int main()
{
    int a, b;
    char s[MAX_SIZE], p[MAX_SIZE];

    printf("請輸出形式串：");
    scanf("%s", &s);
    printf("請輸出子串：");
    scanf("%s", &p);

    a = BFMatch(s, p);
    b = KMPMatch(s, p);

    if(a != -1)
    {
        printf("應用BF算法：%d\n", a);
    }
    else
    {
        printf("未婚配\n");
    }

    if(b != -1)
    {
        printf("應用KMP算法：%d\n", a);
    }
    else
    {
        printf("未婚配\n");
    }

    system("pause");
}

成果

請輸出形式串：lalalalalaaaa
請輸出子串：lalaa
應用BF算法：6
應用KMP算法：6
請按隨意率性鍵持續. . .