9、字符串匹配。设主串数组名为S，子串数组名为T，现在要找出子串T在主串S中第一次出现的位置。c语言代码

在C语言中，可以使用KMP（Knuth-Morris-Pratt）算法或Boyer-Moore算法来高效地解决字符串匹配问题。这里简单介绍KMP算法的步骤：

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

// 定义辅助函数，用于构建部分匹配表
void getPartialMatchTable(char *pattern, int *lps) {
    int index = 0;
    lps[0] = 0; // 空字符串的最长公共前后缀长度为0

    for (int i = 1; pattern[i] != '\0'; i++) {
        if (pattern[i] == pattern[index]) {
            index++;
            lps[i] = index;
        } else {
            if (index != 0)
                index = lps[index - 1];
            else
                lps[i] = 0;
        }
    }
}

// KMP算法查找子串在主串中的位置
int kmpSearch(char *text, char *pattern) {
    int M = strlen(pattern);
    int N = strlen(text);
    int lps[M]; // 存储部分匹配表
    getPartialMatchTable(pattern, lps);

    int i = 0, j = 0;
    while (i < N) {
        if (text[i] == pattern[j])
            i++, j++;
        else if (j != 0)
            j = lps[j - 1];
        else
            i++; // 没有匹配项，移动到下一个字符
    }

    if (j == M) // 如果找到了匹配，返回子串起始位置
        return i - M;
    else
        return -1; // 未找到匹配
}

int main() {
    char S[] = "Hello, World!";
    char T[] = "World";
    int result = kmpSearch(S, T);
    if (result != -1)
        printf("Substring found at position %d\n", result);
    else
        printf("Substring not found.\n");
    return 0;
}

这个程序首先计算了模式串`pattern`的部分匹配表`lps`，然后在主串`text`中按照KMP算法进行匹配。如果找到匹配，它会返回子串的起始位置；如果没有找到，返回-1。