c - 给定一个长字符串数组，如果它们最多相差一个字符，我如何有效地检查给定的子字符串对（给定字符串的）？

Question

任何给定的子串对都具有相同的长度。必须检查许多对子字符串，因此简单的比较不够有效，但我真的想不出任何有助于加快比较过程的字符串数组的预处理。提前致谢！

提供了一个示例以进行说明：

一个长字符串数组：

str = {"aaaaa", "aaabbcc", "abcdefgh"...}

要检查的子串对：

pairs = {(str[0][0..1],str[1][1..2]), (str[0][1..4],str[2][3..6]), (str[1][2..4], str[2][0..2])...}

要检查（替换）的子串对：

pairs = {("aa","aa"), ("aaaa","defg"), ("abb","abc")...}

最终结果：

result = {true, false, true}

一个天真的比较会导致运行时O(|pairs|*max(|str[i]|))，我想改进它。

标签： cstringsubstringstring-matching

Answer 1

（在这里交叉发布我从 Quora 的答案）。

IMO，这个问题没有说得很清楚，但我认为它似乎在问以下问题：我们得到一组字符串 S[1]、S[2]、...、S[N] 和一组查询每个都采用 (i1, j1, i2, j2, L) 的形式。如果从 S[i1] 的位置 j1 和 S[i2] 的位置 j2 开始的长度为 L 的字符串最多相差一个字符，则该查询的答案是“是”，否则为“否”。所有此类查询的 L 值之和可能远大于字符串的总长度。

在这种情况下，我们可以使用以下观察设计一个有效的算法：如果 S 和 T 是长度为 L 的字符串，那么语句“S 和 T 最多相差一个字符”等价于“LCP(S, T) + LCP(R(S), R(T)) >= L-1” 其中 R 表示一个字符串的反转，LCP 是两个字符串的最长公共前缀的长度。

因此，为了有效地回答查询，我们只需要对字符串 S[1], ..., S[N] 和 R(S[1]), ..., R(S[N]) 进行预处理，以便最长公共-prefix 查询很快。这可以通过连接 S[1], ..., S[N] 来给出一个字符串 S，并构建 S 的后缀数组和最长公共前缀数组，然后对 S 的倒数执行相同的操作来完成。那么原始字符串的两个子串的LCP就相当于确定了S(*)的两个子串的LCP，相当于LCP数组中的一个range-minimum-query，可以通过预处理得到有效的回答。类似的陈述适用于原始字符串的反转和 S 的反转。

(*) 从技术上讲，连接字符串 S 中的 LCP 可以超出原始字符串的边界。然而，这只会在查询子字符串实际上相同的情况下发生，所以这只是意味着我们会在答案为“是”的情况下回答“是”。