你好，同学。今天我们来攻克字符串处理中的一个经典基础题——最长公共前缀。

在 NOI 竞赛中，字符串匹配和前缀处理是字符串算法（如 KMP、Trie 字典树）的基石。这道题虽然看似简单，但它能很好地训练你对边界条件的控制以及对多指针同步扫描的理解。

一、 预备知识点

1. 字符串基础操作：掌握 std::string 的长度获取 .size()、子串截取 .substr() 以及字符访问。
2. 双重循环模拟：能够处理“字符串数组”这种二维结构（行是不同的字符串，列是字符位置）。
3. 扫描策略：理解“横向扫描”与“纵向扫描”的逻辑区别。
4. 边界处理：空输入、长度为 1 的输入以及无公共前缀的情况。

二、 题目描述 (NOI 竞赛风格)

题目名称：最长公共前缀 (Longest Common Prefix)

【问题描述】 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 ""。 公共前缀是指所有字符串在起始位置都完全相同的子串。

【输入格式】 第一行包含一个正整数 $n$，表示字符串的数量。 接下来 $n$ 行，每行包含一个仅由小写字母组成的字符串。

【输出格式】 输出一个字符串，表示所有输入字符串的最长公共前缀。如果没有公共前缀，则输出一个空行。

【样例 1 输入】

3
flower
flow
flight

【样例 1 输出】

fl

【样例 2 输入】

3
dog
racecar
car

【样例 2 输出】 (输出为空行)

【数据规模与约定】

• $1 \le n \le 200$
• $0 \le \text{每个字符串的长度} \le 200$
• 字符串仅由小写英文字母组成。

三、 启发式引导：草稿纸上的推理过程

请拿出草稿纸，我们尝试用两种视角来观察这些字符串：

第一步：纵向扫描 (Vertical Scanning) —— 推荐方法

想象把所有字符串像列队一样对齐：

列号: 0 1 2 3 4 5
s1:  f l o w e r
s2:  f l o w
s3:  f l i g h t
     ^ ^ [X] -> 发现第2列(字符'o'和'i')不匹配

思考：

1. 我们先观察所有字符串的第 0 列，如果都一样，看第 1 列。
2. 什么时候停止？
   • 情况 A：某一个字符串到头了（比如 flow 只有 4 位）。
   • 情况 B：在某一列发现了不同的字符。

第二步：横向扫描 (Horizontal Scanning)

先把第一个字符串 s1 暂定为“当前公共前缀” $LCP$。

1. 将 $LCP$ 与 s2 比较，缩短 $LCP$ 为它们两者的公共部分。
2. 将更新后的 $LCP$ 再与 s3 比较，继续缩短。
3. 如果中途 $LCP$ 变成了空，直接结束。

第三步：复杂度分析与思考

• 时间复杂度：最坏情况下（所有字符串完全相同），我们需要遍历所有字符。设 $n$ 为字符串数量，$L$ 为平均长度，复杂度为 $O(n \times L)$，即 $O(S)$，$S$ 是所有字符的总数。
• 空间复杂度：除了存储结果外，我们只需要常数级别的额外空间（纵向扫描）或少量临时变量。

四、 NOI 风格 C++14 伪代码提示

// 引入标准库 string, vector
使用命名空间 标准库;

字符串 函数 获取最长公共前缀(向量<字符串>& 字符串列表) {
    // 边界处理：如果列表为空
    如果 (字符串列表.为空()) 返回 "";

    // 纵向扫描：以第一个字符串为基准
    字符串 基准 = 字符串列表[0];
    对于 列指针 从 0 到 基准长度 - 1 {
        字符 当前待比对字符 = 基准[列指针];
        
        // 遍历剩余的其他字符串
        对于 行指针 从 1 到 列表长度 - 1 {
            字符串 当前串 = 字符串列表[行指针];
            
            // 易错点检查：
            // 1. 如果当前串已经到头了 (列指针 == 当前串长度)
            // 2. 如果当前串在这一列的字符和基准字符不同
            如果 (列指针 等于 当前串长度 或者 当前串[列指针] 不等于 当前待比对字符) {
                // 说明公共部分到此为止，截取基准串的前“列指针”个字符返回
                返回 基准.截取子串(0, 列指针);
            }
        }
    }
    
    // 如果全部跑完没被切断，说明第一个字符串本身就是最长公共前缀
    返回 基准;
}

整型 主函数() {
    // 读取 n，循环读取 n 个字符串存入 vector
    // 调用函数并输出
    返回 0;
}

五、 总结：读题关键词与题型识别

在处理字符串题目时，看到以下关键词要形成条件反射：

1. “前缀” (Prefix)：

   • 意味着必须从下标 0 开始。
   • 考虑使用纵向扫描。
   • 进阶题型可能会涉及 Trie（字典树）。

2. “最长公共” (Longest Common)：

   • 隐含了“单调递减”的性质：随着比较的字符串增多，公共部分的长度只会缩短，不会变长。
   • 如果是在两个长字符串间找公共子串（不一定是前缀），则可能涉及 动态规划 或 后缀数组。

3. “所有” (Amongst all)：

   • 意味着只要有一个不满足，全局就不满足。在循环中可以利用 return 或 break 提前终止，这是优化常数时间的有效手段。

教练点评： 这道题在实战中容易在“空字符串”和“长度为1”的边界上出错。在草稿纸上模拟时，务必画一个长度不等的样例（如 ab 和 abc），确保你的循环边界（是 < 还是 <=）能够正确处理最短的那个字符串。加油！