如何找出N个字符串中共享最长前缀的字符串对？求最优算法

核心思路：排序+相邻比对 #

从渐近复杂度层面，最优方法是先对字符串数组做字典序排序，再遍历相邻字符串计算最长公共前缀（LCP）。

为什么这是最优的？ #

字典序排序后，共享最长前缀的两个字符串必然是相邻的——因为如果两个字符串有很长的共同前缀，它们在字典序中一定是紧挨着的（中间不可能插入一个和它们前缀重叠更长的字符串）。这种方法的渐近复杂度是O(N*L logN)，其中：

• N是字符串的数量
• L是字符串的平均长度
  排序阶段的时间是O(N logN)次字符串比较，每次比较最多O(L)时间；遍历相邻对计算LCP的时间是O(NL)，整体由排序阶段主导，远优于暴力枚举所有字符串对的O(N²L)复杂度。

具体步骤 #

1. 排序数组：将输入数组按字典序排序。比如示例数组排序后为：

   ["banana", "banana pie", "banana smoothie", "pack", "packing"]
   

2. 计算相邻LCP：依次计算每对相邻字符串的最长公共前缀，记录长度最大的那一对：
   • "banana" 和 "banana pie" 的LCP是banana（长度6）
   • "banana pie" 和 "banana smoothie" 的LCP是banana （长度7，这是示例中的最长前缀）
   • "banana smoothie" 和 "pack" 的LCP是空字符串
   • "pack" 和 "packing" 的LCP是pack（长度4）
3. 输出结果：保留LCP长度最大的字符串对即可。

如何找出任意字符串对的最长前缀 #

如果需要找出所有字符串对的最长公共前缀，有两种常用方法：

1. 暴力枚举法：遍历所有N*(N-1)/2对字符串，逐字符比对计算LCP。复杂度O(N²*L)，适合N较小的场景。
2. 前缀树（Trie）法：
   • 先构建前缀树，每个节点存储经过该节点的字符串集合。构建时间O(N*L)。
   • 对于每个字符串，遍历前缀树的路径，在每个节点处记录与该路径上其他字符串的LCP（即当前节点的深度）。这种方法可以批量处理所有字符串对的LCP查询，整体复杂度接近O(N*L)，适合N较大的场景。

内容的提问来源于stack exchange，提问作者Dan Bechard