最长公共前缀（LCP）和最长公共子串（LCS）是字符串匹配和分析中的两个不同概念。
- 前者强调最长前缀；必须从字符串开始匹配
- 后者强调最长子字符串，可从字符串中任何位置开始
最长公共前缀 (LCP)：
- LCP 是两个或多个字符串前缀中最长的字符串。它常用于算法和数据结构中，尤其是在排序和搜索中。
- 例如，给定字符串 "apple"、"appitizer "和 "apricot"，LCP 就是 "ap"。
有几种算法可以找到 LCP，每种算法的时间和空间复杂度各不相同。下面是几种常见的算法：
- 暴力法：这种简单的算法将一个字符串的所有可能前缀与另一个字符串进行比较，然后返回匹配的最长前缀。虽然容易实现，但其时间复杂度为 O(nm)，其中 n 是最短字符串的长度，m 是最长字符串的长度。
- 水平扫描：该算法逐个字符横向比较字符串的字符，并返回迄今为止遇到的最长公共前缀。它的时间复杂度为 O(nm)，但所需空间比蛮力法少。
- 二进制搜索：该算法使用二进制搜索来查找 LCP。它首先找到 LCP 的最小长度，然后使用二进制搜索找到匹配该长度所有字符串的最长前缀。该算法的时间复杂度为 O(n log m)。
- Trie：该算法使用 trie 数据结构来高效地存储和比较字符串。它对大型字符串集特别有效，时间复杂度为 O(nm)。
下面是一段简单的 暴力法Python 代码，用于查找字符串数组的 LCP：
def longest_common_prefix(strings):
if not strings:
return ""
prefix = strings[0]
for string in strings[1:]:
i = 0
while i < len(prefix) and i < len(string) and prefix<i> == string<i>:
i += 1
prefix = prefix[:i]
return prefix
|
下面是Java代码：
public static String findLongestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
while (strs<i>.indexOf(prefix) != 0) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) {
return "";
}
}
}
return prefix;
|
Trie树
Trie树（也称为前缀树或数字树）是专门为存储和查询字符串集而设计的数据结构。
Trie树的优点在于它可以让你高效地找到字符串的公共前缀，因为它以树的形式存储它们，其中多个字符串的公共前缀是树中的公共路径。
基于Trie树的算法通常比基于逐个字符比较的方法具有更好的性能。
class TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
boolean isEndOfWord = false;
}
class TrieNodeMain {
public static String findLongestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
TrieNode root = new TrieNode();
for (String str : strs) {
TrieNode node = root;
for (char c : str.toCharArray()) {
node.children.putIfAbsent(c, new TrieNode());
node = node.children.get(c);
}
node.isEndOfWord = true;
}
StringBuilder prefix = new StringBuilder();
TrieNode node = root;
while (node.children.size() == 1 && !node.isEndOfWord) {
Map.Entry<Character, TrieNode> entry = node.children.entrySet().iterator().next();
prefix.append(entry.getKey());
node = entry.getValue();
}
return prefix.toString();
}
}
|
上面的方法接受一个字符串数组作为参数。检查数组是否为空后，初始化Trie树节点。下一步将迭代提供的字符串，然后迭代当前字符串中的字符。在循环中，如果尚不存在，则为每个字符添加一个新节点。创建一个StringBuilder对象来保存生成的前缀。最后，在while循环中查找最长的前缀。
最长公共子串 (LCS)
两个字符串的最长公共子串（LCS）是两个字符串的最长子串
- LCS 是由两个或多个字符串组成的最长字符串。换句话说，它是在所有给定字符串中以相同顺序出现的最长字符序列。
- 例如，给定字符串 "abcdef "和 "abcde"，LCS 就是 "abcde"。
查找 LCS 的算法：
- 动态编程：这是最常见的 LCS 查找算法。它创建了一个表格，其中每个单元格代表每个字符串以该点结尾的子串的 LCS 长度。然后，该算法考虑所有可能的字符及其相应的 LCS 长度，反复填充表格。该算法的时间复杂度为 O(nm)，空间复杂度为 O(nm)。
- 后缀树：该算法为其中一个字符串建立后缀树，然后使用后缀树高效查找 LCS。其时间复杂度为 O(n log n)，空间复杂度为 O(n)。
def longest_common_substring(str1, str2):
m, n = len(str1), len(str2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_len, end_index = 0, 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
dp<i>[j] = dp[i - 1][j - 1] + 1
if dp<i>[j] > max_len:
max_len = dp<i>[j]
end_index = i - 1
else:
dp<i>[j] = 0
return str1[end_index - max_len + 1:end_index + 1]
|
Java代码：
public static String lcs(String s1, String s2) {
int m = s1.length();
int n = s2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
dp<i>[j] = 0;
} else if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp<i>[j] = dp[i - 1][j - 1] + 1;
} else {
dp<i>[j] = Math.max(dp[i - 1][j], dp<i>[j - 1]);
}
}
}
int lcsLength = dp[m][n];
char[] lcs = new char[lcsLength];
int i = m, j = n;
while (i > 0 && j > 0) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
lcs[lcsLength - 1] = s1.charAt(i - 1);
lcsLength--;
i--;
j--;
} else if (dp[i - 1][j] > dp<i>[j - 1]) {
i--;
} else {
j--;
}
}
return new String(lcs);
}
|
上面的源代码片段使用动态规划计算两个字符串text1 和text2 之间的最长公共子串。该算法循环遍历两个字符串，创建一个dp 数组来存储中间结果。然后，它使用dp数组重新创建最长的公共子字符串。
上述算法可用于解决诸如比较文本文档、分析 DNA 序列、管理软件版本等问题。此外，[LCS] 还可用于需要查找两个字符串之间的公共序列的各种领域。该算法是有效的并且具有许多实际应用。