给定两个字符串S=“abcdefghi” 和T=“hi”，在主串S中查找模式串T的过程称为串匹配，也叫做模式匹配。如果T是S的子串，返回T在S中首次出现的位置，如若不是则返回-1

Question

给定两个字符串S=“abcdefghi”  和T=“hi”，在主串S中查找模式串T的过程称为串匹配，也叫做模式匹配。如果T是S的子串，返回T在S中首次出现的位置，如若不是则返回-1

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

串匹配算法

串匹配算法是指在主串中查找模式串的过程。常见的串匹配算法有KMP算法、BM算法、Rabin-Karp算法等。

下面使用KMP算法实现串匹配：

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

int KMPSearch(char *S, char *T) {
    int i = 0, j = 0;
    int m = strlen(T);
    int n = strlen(S);

    int lps[m]; // lps数组，用于记录T的前缀和后缀的最长公共前缀
    lps[0] = 0;
    int k = 0;
    while (i < m) {
        if (T[i] == T[k]) {
            i++;
            k++;
            lps[k] = k;
        } else if (k != 0) {
            k = lps[k - 1];
        } else {
            i++;
        }
    }

    i = 0;
    j = 0;
    while (i < n) {
        if (S[i] == T[j]) {
            i++;
            j++;
        } else if (j != 0) {
            j = lps[j - 1];
        } else {
            i++;
        }
        if (j == m) {
            return i - m;
        }
    }
    return -1;
}

int main() {
    char S[] = "abcdefghi";
    char T[] = "hi";
    int pos = KMPSearch(S, T);
    if (pos != -1) {
        printf("T在S中首次出现的位置是：%d\n", pos);
    } else {
        printf("T不是S的子串\n");
    }
    return 0;
}

输出结果：

T在S中首次出现的位置是：7

代码解释

1. 首先，我们定义了一个函数KMPSearch，用于实现串匹配。
2. 在KMPSearch函数中，我们首先计算模式串T的前缀和后缀的最长公共前缀，并将其存储在lps数组中。
3. 然后，我们使用lps数组来实现串匹配。我们从主串S的开始位置开始匹配，直到找到模式串T的首次出现位置。
4. 如果模式串T不是主串S的子串，我们返回-1。

时间复杂度

KMP算法的时间复杂度是O(n+m)，其中n是主串的长度，m是模式串的长度。