KMP和BF算法-C语言实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
//以下为KMP算法
void get_next(char * T, int next[])   //修正前的next数组
{
    int i = 1, j = 0;
    next[0] = -1;
    next[1] = 0;
    int m = strlen(T);
    while (i<strlen(T) - 1)
    {
        if (j == -1 || T[j] == T[i])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else j = next[j];
    }
}
void get_nextval(char * T, int nextval[]) //修正后的nextval数组
{
    int i = 1, j = 0;
    nextval[0] = -1;
    nextval[1] = 0;
    int m = strlen(T);
    while (i<strlen(T) - 1)
    {
        if (j == -1 || T[j] == T[i])
        {
            ++i;
            ++j;
            if (T[i] != T[j]) nextval[i] = j;
            else nextval[i] = nextval[j];
        }
        else j = nextval[j];
    }
}
int Index_KMP(char * S, char * T, int pos, int next[])   //逐项比较
{
    int j = 0, i = pos, lens = strlen(S), lent = strlen(T);
    get_next(T, next);
    while (i < lens && j < lent)
    {
        if (S[i] == T[j] || j == -1)
        {
            i++; j++;
        }
        else j = next[j];
    }
    if (j >= lent) return i - lent;
    else return -1;
}

//以下为BF算法
int Pos_BF(char * S, char * T)
{
    int pos = 1;
    for (int i = 0; i < strlen(S); i++)
    {
        if (S[i] == T[0])
            return pos;
        else
            pos++;
    }
    return 0;
}
int Index_BF(char * S, char * T)
{
    int i = 0, j = 0;
    int lens = strlen(S), lent = strlen(T);
    while (i <= lens -1  && j <= lent -1 )
    {
        if (S[i] == T[j])
        {
            ++i;
            ++j;
        }
        else
        {
            i = i - j + 1;
            j = 0;
        }
    }
    //跳出循环有两种可能，i=lens说明已经遍历完主串，匹配失败；j=lent,说明子串遍历完成，在主串中成功匹配
    if (j == lent) {
        return i - lent + 1;
    }
    //运行到此，为i==lens的情况
    return -1;
}


int main()
{
    //char *S = "adbadabbaabadabbadada", *T = "adabbadada";
    char S[30];
    char T[20];
    printf("请输入两个字符串进行匹配：\n");
    printf("请输入母串：");
    scanf("%s", S);
    printf("请输入匹配串：");
    scanf("%s", T);
    //此处开始测试KMP算法
    printf("\n**********************KMP算法**************************\n");
    int m;
    int *next = (int *)malloc((strlen(T) + 1)*sizeof(int));   //修正前的next数组
    int *nextval = (int *)malloc((strlen(T) + 1)*sizeof(int));    //修正后的nextval数组
    get_next(T, next);
    printf("修正前next数组为：");
    for (m = 0; m<strlen(T); m++)
    {
        printf("%d ", next[m] + 1);
    }
    get_nextval(T, nextval);
    printf("\n修正后的nextval数组为：");
    for (m = 0; m<strlen(T); m++)
    {
        printf("%d ", nextval[m] + 1);
    }
    int t1 = Index_KMP(S, T, 0, nextval);
    if (t1 == -1) printf("\n无匹配项！\n");
    else
    {
        printf("\n在第%d项开始匹配成功\n", t1 + 1);
    }
    //此处开始测试BF算法
    printf("\n**********************BF算法**************************\n");
    int t2 = Index_BF(S, T);
    printf("\n在第%d项开始匹配成功\n", t2);
    system("pause");
    return 0;
}