1. LCP基础概念与暴力解法
LCP（Longest Common Prefix）是指两个或多个字符串从首字符开始连续匹配的最长子串。例如，字符串 "flower" 和 "flow" 的LCP是 "flow"，而 "dog" 与 "racecar" 的LCP为空。
最直接的计算方法是暴力逐字符比较：
从第一个字符开始，依次比较每个位置的字符是否相同。一旦遇到不同字符或任一字符串结束，即停止。时间复杂度为 O(n)，其中 n 是较短字符串的长度。
def lcp_brute_force(strs):
if not strs:
return ""
prefix = strs[0]
for s in strs[1:]:
i = 0
while i < len(prefix) and i < len(s) and prefix[i] == s[i]:
i += 1
prefix = prefix[:i]
return prefix
该方法适用于少量字符串场景，但在高频查询中效率低下。
2. 多字符串LCP的优化策略
当处理一组字符串时，可先排序后比较相邻字符串的LCP，利用字典序性质缩小搜索空间。
关键观察：若字符串已按字典序排列，则整体LCP必为第一个和最后一个字符串的LCP。
字符串集合排序后LCP["flower","flow","flight"]["flight","flow","flower"]"fl"["apple","apply","appetite"]["appetite","apple","apply"]"app"["dog","cat","bird"]["bird","cat","dog"]""
此方法将多串LCP问题简化为两次两两比较，时间复杂度仍为O(n)，但常数因子更优。
3. 后缀数组中的LCP数组构建
在构建后缀数组（Suffix Array）时，LCP数组用于记录相邻后缀间的最长公共前缀长度。
设 SA[i] 表示排名第 i 的后缀起始位置，LCP[i] = |lcp(SA[i], SA[i-1])|。
Kasai算法可在 O(n) 时间内由后缀数组构造LCP数组：
遍历原字符串每个位置作为后缀起点。利用已知LCP值跳过重复比较（利用LCP的单调性）。维护当前匹配长度 h，并逐步递减更新。
def build_lcp_array(s, sa):
n = len(s)
rank = [0] * n
for i in range(n):
rank[sa[i]] = i
lcp = [0] * n
h = 0
for i in range(n):
if rank[i] > 0:
j = sa[rank[i]-1]
while i+h < n and j+h < n and s[i+h] == s[j+h]:
h += 1
lcp[rank[i]] = h
if h > 0:
h -= 1
return lcp
4. LCP查询优化：RMQ结合Sparse Table
为了实现任意两后缀间LCP的O(1)查询，需结合LCP数组与RMQ（Range Minimum Query）。
核心思想：任意两个后缀的LCP等于其在后缀数组中对应区间内的最小LCP值。
graph TD
A[原始字符串] --> B[构建后缀数组SA]
B --> C[构建LCP数组]
C --> D[构建Sparse Table for RMQ]
D --> E[O(1) LCP查询]
RMQ预处理使用Sparse Table，支持静态数组上的区间最小值查询：
预处理时间：O(n log n)空间复杂度：O(n log n)查询时间：O(1)
import math
class SparseTable:
def __init__(self, arr):
self.n = len(arr)
self.k = math.floor(math.log2(self.n)) + 1
self.st = [[0]*self.k for _ in range(self.n)]
for i in range(self.n):
self.st[i][0] = arr[i]
for j in range(1, self.k):
for i in range(self.n - (1 << j) + 1):
self.st[i][j] = min(self.st[i][j-1], self.st[i + (1 << (j-1))][j-1])
def query(self, l, r):
j = math.floor(math.log2(r - l + 1))
return min(self.st[l][j], self.st[r - (1 << j) + 1][j])
5. 实际应用场景分析
LCP技术广泛应用于多个领域：
领域应用关键技术生物信息学基因序列比对后缀数组 + LCP数据压缩LZ77/LZSS算法滑动窗口内查找最长匹配全文检索倒排索引优化Trie树路径压缩代码编辑器自动补全Trie + LCP预测版本控制系统差异检测基于后缀结构的相似度分析
例如，在Trie树中，插入和查询操作天然涉及前缀匹配；通过存储子节点的LCP信息，可实现Patricia Trie等压缩形式，显著降低内存占用。
