📝 题目大意

给定字符串 $S$ 和 $T$，已知 $T$ 是在 $S$ 的某个位置插入一个小写字母得到的。找出插入的字母在 $T$ 中是从首字母开始的第几个字符（即 $1$ 索引的位置）。

💡 解题思路

1. 题目分析：$|T| = |S| + 1$，且 $S$ 与 $T$ 仅有一个字符的差异。由于 $T$ 是在 $S$ 中插入一个字符得到的，因此 $S$ 和 $T$ 的字符在插入位置之前完全相同，从插入位置开始 $S$ 的字符相对于 $T$ 会整体向后偏移一位。

2. 算法推导：

   • 设 $S$ 为 n，$T$ 为 m。
   • 从头开始同时扫描 $S$ 和 $T$，即比较 n[i] 与 m[i]（$i$ 从 $0$ 开始）。
   • 第一个满足 n[i] != m[i] 的位置 $i$ 就是插入发生的位置——此时 m[i] 即为被插入的字符。
   • 输出 $i + 1$（因为题目要求 $1$ 索引）。
   • 若插入位置在末尾（即 $S$ 的所有字符与 $T$ 的前 $|S|$ 个字符完全匹配），则当 $i = |S|$ 时，n[|S|] 访问到字符串末尾的 '\0'，而 m[|S|] 是 $T$ 的最后一个字符，两者必然不同，因此输出 $|S| + 1 = |T|$，同样正确。

3. 边界与细节：

   • $|S| \ge 1$，$|T| \ge 2$，循环条件 i <= m.size()-1 中的 m.size()-1 不会发生无符号下溢。
   • 题目允许任意合法位置输出，因此找到第一个不匹配位置直接输出并 break 即可。
   • 由于 C++ 中 std::string 的 operator[] 不进行越界检查，在末尾插入的情况下访问 n[|S|] 会得到 '\0'，不会引发运行时错误，且逻辑正确。

⏱️ 复杂度分析

• 时间复杂度：$O(|S|)$，最坏情况下需要遍历整个 $S$（当插入位置在末尾时）。
• 空间复杂度：$O(|S| + |T|)$，用于存储两个输入字符串。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
int main(){
	string n, m;          // n = S, m = T
	cin >> n >> m;
	// 从头扫描，找到第一个不匹配的位置
	for (int i = 0; i <= m.size() - 1; i++) {
		if (n[i] != m[i]) {     // 插入发生在此处
			cout << i + 1;      // 输出 1 索引的位置
			break;              // 任意一个合法位置即可，找到即退出
		}
	}
	return 0;
}