字符串的快速模式匹配(KMP算法)

#include <stdio.h>

// 顺序存储的字符串
#define MAX_SIZE 100
typedef struct
{
    char str[MAX_SIZE];
    int length;
}seqString;

// 1.顺序字符串的初始化
void init(seqString *str)
{
    str->length = 0;
}

// 2.根据用户输入构造字符串
void insert(seqString *str)
{
    char c;
    printf("请输入字符，回车表示结束输入...\n");
    while ((c = getchar()) != '\n' && str->length < MAX_SIZE)
        str->str[str->length++] = c;
}

// 根据模式串求对应的next数组
void getNext(seqString p,int next[])
{
    int i = 0, j = -1;
    next[0] = -1;
    while (i < p.length)
    {
        if(j == -1 || p.str[i] == p.str[j])
        {
            i++;
            j++;
            next[i] = j;
        } else j = next[j];
    }
}

// 4.2.2 字符串的KMP模式匹配算法
// 如果成功则返回p在t中首次出现的起始位置，否则返回-1
int kmp(seqString t, seqString p,int next[])
{
    int i = 0,j = 0;
    while (i < t.length && j <p.length)
    {
        if(j == -1 || t.str[i] == p.str[j])
        {
            i++;
            j++;
        } else j = next[j];
    }
    if(j == p.length) return i-p.length;
    return -1;
}

int main()
{
    seqString t,p;
    init(&t); init(&p);
    insert(&t);
    insert(&p);
    int next[p.length];
    getNext(p,next); // 求p的next数组
    int i = kmp(t,p,next);
    if(i == -1)
        printf("模式串匹配失败！\n");
    else printf("模式串在主串中首次出现的起始位置是%d",i);
    return 0;
}