最长匹配子字符串,与字符顺序无关

Question

我无法找到以下假设面试问题的答案:

给定两个长度为N的字符串序列,如何找到匹配子字符串的最大长度,而不管顺序如何.

例如,给定seq1 = "ABCDEFG",并且seq2 = "DBCAPFG",最大长度窗口是4.(ABCD来自seq1和DBCA来自seq2).

Answer 1

这是一个O(n)解决方案(假设固定的字母大小和O(1)字典访问).

使用单个频率表来计算seq1中的字符,向下计算seq2中的字符.如果此直方图再次采用相同的值,我们将有一个匹配的窗口(因为这意味着我们必须具有相同数量的中间字符).

所以我们使用字典来存储直方图的先前值.

Python实现:

def find_window(seq1,seq2):
    """Yield length of matching windows"""
    D={} # Dictionary with key=histogram, value = first position where this happens
    H=[0]*26 # H[x] is count of x in seq1 - count of x in seq2
    D[tuple(H)]=-1
    for i,(a,b) in enumerate(zip(seq1,seq2)):
        a=ord(a)-ord('A')
        b=ord(b)-ord('A') 
        H[a]+=1
        H[b]-=1
        key=tuple(H)
        if key in D:
            yield i-D[key]
        if key not in D:
            D[key]=i

print max(find_window("ABCDEFG","DBCAPFG"))

如果你有一个更大的字母表,你可以使用类似的技术只存储哈希值而不是完整的直方图.例如,您可以简单地为每个字符选择一个随机代码,并为seq中的每个字母添加代码,或者为seq2中的字母减去.

在发生哈希冲突时,您需要第二次传递来检查建议的匹配是否正确.

Answer 2

假设

对于给定数组 A[0..n], B[0..m]

• 有限字母表

• 非重复字符

   ans = -1
   j = index of A[0] in B
   if j > n then no substring exists
   for 1 .. n
       find A[i] in B[0..j]
       if not found
           j = find A[i] in B[j+1..m]
           if not found, return last ans
       else 
           if i == j then ans = j
  

如果 B[0..j] 已排序（可能构造二叉树 P），则在 B[0..j] 中搜索 A[i] 将是 O(log n)，整个算法将是 O(n log n)

帮助验证这一点会很棒。
有什么反例吗？