数据结构-串：KMP模式匹配算法

题目：1366: KMP字符串模式匹配算法

描述：KMP算法是字符串模式匹配算法中较为高效的算法之一，其在某次子串匹配母串失败时并未回溯母串的指针而是将子串的指针移动到相应的位置。严蔚敏老师的书中详细描述了KMP算法，同时前面的例子中也描述了子串移动位置的数组实现的算法。前面你已经实现了子串移动的数组，现在就来利用该数组来实现KMP模式匹配。

输入: 3组字符串，每组字符串占一行。每行包含由空格分隔的两个字符串，字符串仅由英文小写字母组成且长度不大于100。

image.png

#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

// KMP算法,打印next数组
void showNext(int *next, int len) {
//    printf("T\ti\tnext\n");
    int i = 1;
    while (i <= len) {
        printf("%d ", next[i++]);
    }
    printf("\n");
}

/**
 * 前缀：包含第一个字符，且不包含最后一个字符的子串
 * 后缀：包含最后一个字符，且不包含第一个字符的子串
 * next[j] = T 的最长相等前后缀长度+1
 * 特别的：next[1]=0
 *      next 数组为了方便使用，空出 下标为0的位置，从1开始填充数据
 *  【例】
 *  --------------------------------------------
 *  * J      |  1  |  2  |  3  |  4  |  5  |  6
 *  * T      |  a  |  b  |  a  |  b  |  a  |  a
 *  * next   |  0  |  1  |  1  |  2  |  3  |  4
 *  --------------------------------------------
 * @param T ：模式串
 * @param next ：next数组
 */
void getNext(string T, int next[]) {
    int i = 1; // 后缀
    int j = 0; // 前缀
    int len = T.length();
    next[1] = 0;
    while (i < len) {
        if (0 == j || T[i-1] == T[j-1]) {
            ++i;
            ++j;
            next[i] = j; /** // next数组生成，若注释此行，使用下面注释部分代码为next数组的优化 */
           /*  // next 数组的优化 -> nextval 数组
            if (T[i-1] != T[j-1]) {
                next[i] = j;
            } else {
                next[i] = next[j];
            }*/
        } else {
            j = next[j];
        }
    }
    showNext(next, len);
}

// 返回子串T在主串S第pos个字符之后的位置
int index_KMP(string S, string T, int pos) {
    int i = pos;
    int j = 1;
    int next[T.length() + 1];
    getNext(T, next);
    while (i <= S.length() && j <= T.length()) {
        if (0 == j || S[i] == T[j-1]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j > T.length()) {
        return i - T.length() + 1;
    } else return 0;

}

int main() {
    string s0="0",t0="0";
    string S1, T1, S2, T2, S3, T3;
    cin >> S1 >> T1 >> S2 >> T2 >> S3 >> T3;
    int index = index_KMP(S1, T1, 0);
    printf("%d\n", index);
    index = index_KMP(S2, T2, 0);
    printf("%d\n", index);
    index = index_KMP(S3, T3, 0);
    printf("%d\n", index);

    return 0;
}

运行结果

image.png