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

// 求解next数组（同前）
void getNext(char T[], int next[]) {
    int m = strlen(T);
    int j = 0, k = -1;
    next[0] = -1;
    while (j < m - 1) {
        if (k == -1 || T[j] == T[k]) {
            j++;
            k++;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
}

// KMP算法实现
int kmp(char S[], char T[]) {
    int n = strlen(S);  // 主串长度
    int m = strlen(T);  // 模式串长度

    // 边界情况处理
    if (m == 0) return 0;
    if (m > n) return -1;

    int *next = (int *)malloc(m * sizeof(int));  // 动态分配next数组
    getNext(T, next);  // 求解next数组

    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || S[i] == T[j]) {  // j=-1表示需移动主串指针
            i++;
            j++;
        } else {
            j = next[j];  // 模式串指针跳转，主串不回溯
        }
    }

    free(next);  // 释放动态内存，避免泄漏
    return (j == m) ? (i - j) : -1;
}

// 测试示例
int main() {
    char S[] = "abcdeabc";
    char T[] = "bcd";
    int pos = kmp(S, T);
    if (pos != -1) {
        printf("模式串在主串中的起始位置：%d\n", pos);  // 输出0
    } else {
        printf("匹配失败\n");
    }
    return 0;
}
