本专栏持续输出数据结构题目集，欢迎订阅。
题目
请编写程序，得到模式串 t 在主串 s 中首次出现的位置。
本题旨在测试各种不同的匹配算法在各种数据情况下的表现。各组测试数据特点如下：
- 数据0：小规模字符串，测试基本正确性；
- 数据1：随机数据，String 长度为 10^5，Pattern 长度为 10；
- 数据2：随机数据，String 长度为 10^5，Pattern 长度为 10
^2； - 数据3：随机数据，String 长度为 10^5，Pattern 长度为 10
^3； - 数据4：随机数据，String 长度为 10^5，Pattern 长度为 10
^4； - 数据5：String 长度为 10^6，Pattern 长度为 10
^5；测试尾字符不匹配的情形； - 数据6：String 长度为 10^6，Pattern 长度为 10
^5；测试首字符不匹配的情形。
输入格式：
输入先后给出主串 s 和模式串 t，每个非空字符串占一行，以回车结束（回车不算在字符串内）。
输出格式：
如果匹配成功，则输出 s 从 t 首次出现的位置开始的子串；否则输出 匹配失败。。
输入样例 1：
This is a simple test.
is
输出样例 1：
is is a simple test.
输入样例 2：
This is a test.
simple
输出样例 2：
匹配失败。
代码
#include <stdio.h>
const int cnt = 1000000;
// KMP算法的预处理函数：计算部分匹配表（next数组）
void build(char* p, int m, int next[]) {
next[0] = -1; // 初始化next数组
int k = -1; // 前缀长度
// 构建next数组，长度为m-1
for(int j = 0; j < m - 1; j++) {
// 若字符不匹配，回溯到上一个可能的位置
while(k >= 0 && p[j] != p[k])
k = next[k];
k++;
next[j + 1] = k; // 记录当前位置的最长公共前后缀长度
}
}
// KMP字符串匹配主函数
int kmp(int n, int m, char* s, char *p) {
int i = 0; // 主串指针
int j = 0; // 模式串指针
int next[cnt];
// 预处理模式串，构建next数组
build(p, m, next);
// 双指针遍历主串和模式串
while(i < n && j < m) {
// 当前字符匹配或需要从头开始匹配
if(j == -1 || s[i] == p[j]) {
i++;
j++;
} else {
// 字符不匹配，利用next数组回退模式串指针
j = next[j];
}
}
// 匹配成功返回起始位置，否则返回-1
return (j == m) ? i - m : -1;
}
int main() {
char p[cnt]; // 模式串
char s[cnt]; // 主串
int n = 0; // 主串长度
int m = 0; // 模式串长度
// 读取主串（不包含换行符）
while ((s[n] = getchar()) != '\n') {
n++;
}
// 读取模式串（不包含换行符）
while ((p[m] = getchar()) != '\n') {
m++;
}
// 执行KMP匹配
int q = kmp(n, m, s, p);
// 输出匹配结果
if (q != -1) {
// 输出从匹配位置开始的子串
for (int i = q; i < n; i++) {
printf("%c", s[i]);
}
printf("\n");
} else {
printf("匹配失败。\n");
}
return 0;
}