Amazon 实现Grep：逐行过滤与明确匹配合同

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 题目要求实现grep但完整长题干未保留，flags/regex/文件处理约束缺失。练习先定义精确大小写的literal子串匹配，支持invert，返回一基行号和原行。
• lines由调用者提供逐行字符串，保留原行结束符；空pattern匹配每行。不伪装为系统grep的全部命令行、二进制和编码语义。

解题路线

1. enumerate(lines,1)维护行号，以pattern in line判断字面子串；matched!=invert决定输出。generator逐行产出，不必保存所有匹配结果。
2. 行号按全部输入递增，不能只按匹配行编号。输出原行而非strip后的字符串，避免删除缩进、空格和末尾换行。
3. 文本解码/读文件和匹配逻辑分离，方便注入行流及定义坏编码处理。超长单行仍需要容纳整行；若要求严格内存上限，需要分块并维护跨块匹配状态。
4. 正则扩展应单独定义语法和匹配是否跨行，编译一次并控制病态模式成本。大小写不敏感需要明确ASCII还是Unicode归一化，不直接lower就宣称兼容所有语义。

手动走一遍

lines=[alpha换行,beta换行,alphabet]，pattern=alpha输出行1和3。空pattern输出全部，invert空pattern无输出；行2仍保持编号2而非“第二个匹配”。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def grep_literal(lines,pattern,invert=False):
    """Yield (1-based line number, original line), exact literal substring."""
    for number,line in enumerate(lines,1):
        matched=pattern in line
        if matched!=invert:yield number,line

复杂度

设全部字符量T、最长行L、模式P，扫描开销O(行数)，子串匹配的保守朴素上界O(T×max(1,P))，具体Python字符串搜索由实现决定。generator额外O(1)索引状态，读行缓冲O(L)，若收集结果还需输出空间。

易错点与追问

容易失分的边界

• 对每行strip改变要展示的证据。
• 把空模式判成非法，却未先定义。
• 只测试substring示例就声称支持完整grep regex/CLI。

继续深挖

• 怎样返回匹配上下文并去重相邻上下文块？
• 多个文件如何输出文件名且保持每文件行号？
• 对于巨量literal扫描，何时需要KMP或多模式Aho–Corasick？