最长公共子串 (LCS)

最长公共子串（Longest Common Substring）是字符串处理领域的核心算法问题，旨在识别多个字符串中长度最大且字符位置连续的公共片段。与允许字符跳跃的“最长公共子序列”不同，子串严格要求连续性。该问题最早可追溯至文本编辑距离计算，现代算法演进中，动态规划提供了基础解法，而广义后缀树（Generalized Suffix Tree）则通过构建线性时间复杂度的数据结构，实现了大规模多字符串的高效比对，成为生物信息学与大规模日志分析的关键技术基石。

在现代计算架构中，最长公共子串算法扮演着“模式匹配引擎”的角色，其核心价值在于将非结构化的文本数据转化为可量化的相似度指标。它不仅是基础算法竞赛中的高频考点，更是工业界解决版本控制差异、DNA 序列比对、代码 diff 生成及搜索引擎倒排索引构建的底层逻辑。随着大数据时代的到来，该算法从传统的 O(nm) 动态规划向基于后缀自动机（SAM）或后缀树的线性/准线性复杂度演进，极大地提升了海量文本数据的实时处理效率，是构建高吞吐文本分析系统的必要组件。