### 最长公共前缀与后缀的Python实现 #### 1. 最长公共前缀 (Longest Common Prefix) 为了找到一组字符串的最长公共前缀，可以采用多种方法。其中一种简单有效的方法是 **纵向扫描法**[^1]。 以下是基于纵向扫描法的Python实现： ```python def longest_common_prefix(strs): if not strs: return "" # 假设第一个字符串是最长公共前缀 prefix = strs[0] for s in strs[1:]: while s[:len(prefix)] != prefix and prefix: prefix = prefix[:-1] if not prefix: break return prefix ``` 上述代码通过逐步缩短假设的公共前缀 `prefix` 来寻找真正的公共部分。这种方法的时间复杂度为 O(S)，其中 S 是所有字符串中字符总数的总和。 --- #### 2. 最长公共后缀 (Longest Common Suffix) 对于最长公共后缀问题，可以通过反转每个字符串并将问题转化为最长公共前缀问题来解决。具体做法如下： ```python def reverse_string(s): return s[::-1] def longest_common_suffix(strs): reversed_strs = [reverse_string(s) for s in strs] suffix = reverse_string(longest_common_prefix(reversed_strs)) return suffix ``` 这里的关键在于先将输入字符串列表中的每一个字符串反转，再调用之前定义的 `longest_common_prefix` 函数计算这些反转后的字符串的最长公共前缀。最后再次反转结果即可得到原始字符串的最长公共后缀[^3]。 --- #### 3. 组合解决方案：同时获取最长公共前缀与后缀 如果需要同时获得最长公共前缀和后缀，则可以直接组合以上两个函数： ```python def find_longest_common_prefix_and_suffix(strs): lcp = longest_common_prefix(strs) lcs = longest_common_suffix(strs) return {"Prefix": lcp, "Suffix": lcs} # 测试数据 strings = ["flower", "flow", "flight"] result = find_longest_common_prefix_and_suffix(strings) print(result) ``` 运行此程序将会返回给定字符串集合的最长公共前缀以及最长公共后缀。 --- #### 4. 使用KMP算法优化最长公共前后缀匹配 更高效的解决方案可能涉及使用 KMP（Knuth-Morris-Pratt）算法中的 LPS 数组（最长前缀后缀数组）。LPS 数组记录了模式串与其自身的最大重叠长度，这正是我们需要的信息之一。 下面是利用 KMP 的 LPS 构建方式的一个例子： ```python def compute_lps_array(pattern): length = 0 # 当前已知的最大相同前后缀长度 i = 1 # 遍历指针起始位置 n = len(pattern) lps = [0] * n while i < n: if pattern[i] == pattern[length]: length += 1 lps[i] = length i += 1 else: if length != 0: length = lps[length - 1] else: lps[i] = 0 i += 1 return lps[-1], pattern[:lps[-1]] pattern = "abcabca" max_overlap_length, max_overlap_substring = compute_lps_array(pattern) print(f"Max Overlap Length: {max_overlap_length}, Substring: '{max_overlap_substring}'") ``` 该片段展示了如何从单个字符串内部提取其最大的共同前缀和后缀。 ---