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]|))，我想改进这一点。

Answer 1

(交叉发布我在 Quora 上的回答)。

IMO，这个问题没有说得很清楚，但我认为它似乎在问以下问题:我们给出了一组字符串 S[1]、S[2]、...、S[N] 和一个一组查询，每个查询的形式为 (i1, j1, i2, j2, L)。如果从 S[i1] 的位置 j1 开始的长度为 L 的字符串与从 S[i2] 的位置 j2 开始的长度 L 的字符串至多有一个字符的变化不同，则对此类查询的答案为"is"，否则为“否”。所有此类查询的 L 值之和可能远大于字符串的总长度。

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

因此，为了高效地回答查询，我们只需要对字符串 S[1], …, S[N] 和 R(S[1]), …, R(S[N]) 进行预处理，这样最长公共(public)前缀查询速度很快。这可以通过连接 S[1], …, S[N] 给出一个字符串 S，并构建 suffix array 来完成。和 longest-common-prefix array的S，然后对S的逆过程进行相同的操作。确定原始字符串的两个子字符串的LCP相当于确定S(*)的两个子字符串的LCP，这相当于S中的范围最小查询LCP数组，通过预处理可以高效地回答。类似的说法也适用于原始字符串的反转和 S 的反转。

(*) 从技术上讲，连接字符串 S 中的 LCP 可以超出原始字符串的边界。但是，只有当查询子字符串实际上相同时才会发生这种情况，因此这仅意味着在答案为"is"的情况下我们会回答"is"。