PTA6-1 KMP算法

KMP算法是一种字符串匹配算法，用于在一个主串S内查找一个子串T的出现位置。KMP算法的核心是next数组，next数组记录了模式串T中每个前缀的最长相等前后缀的长度。在匹配过程中，当主串S的某个字符与模式串T的某个字符不匹配时，可以利用next数组中记录的信息，将模式串T向右移动一定的位数，从而避免了暴力匹配的重复比较。

以下是PTA6-1 KMP算法的代码实现：

void get_nextval(char T[], int next[]) {
    next[1] = 0;
    for(int i = 2; i <= T[0]; i++) {
        int x = next[i - 1];
        while(x && T[i] != T[x + 1]) {
            x = next[x];
        }
        if(T[i] == T[x + 1]) {
            ++x;
        }
        next[i] = x;
    }
}

int Index_KMP(char S[], char T[], int pos, int next[]) {
    int x = 0;
    for(int i = pos; i <= S[0]; i++) {
        if(S[i] == T[x + 1]) {
            ++x;
            if(x == T[0]) {
                return i - T[0] + 1;
            }
            continue;
        }
        while(x && T[x + 1] != S[i]) {
            x = next[x];
        }
        if(T[x + 1] == S[i]) {
            ++x;
        }
    }
    return 0;
}