#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
請按任意鍵繼續. . .