khớp dài nhất substring không phụ thuộc vào thứ tự của ký tự

Question

tôi không thể tìm thấy câu trả lời cho cuộc phỏng vấn giả câu dưới đây:

Cho hai chuỗi chuỗi có độ dài N, làm thế nào bạn có thể tìm thấy chiều dài tối đa của chuỗi con phù hợp với bất kỳ thứ tự .

Ví dụ, cho seq1 = "ABCDEFG", và seq2 = "DBCAPFG", cửa sổ dài tối đa là 4. (ABCD từ seq1 và DBCA từ seq2).

Answer 1

Asumptions

Đối với mảng đã cho A [0..n], B [0..m]

• bảng chữ cái hữu hạn

• không lặp lại ký tự

  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 
  

nếu B [0..j] là s orted (có thể xây dựng cây nhị phân P), sau đó tìm kiếm A [i] trong B [0..j] sẽ là O (log n) và toàn bộ thuật toán sẽ là O (n log n)

Trợ giúp xác thực điều này sẽ rất tuyệt.
Bất kỳ đối sánh nào?

Answer 2

Đây là giải pháp O (n) (giả sử kích thước bảng chữ cái cố định và truy cập từ điển O (1)).

Sử dụng một bảng tần số duy nhất đếm số ký tự trong seq1 và xuống cho các ký tự trong seq2. Chúng ta sẽ có một cửa sổ phù hợp nếu biểu đồ này lại có cùng giá trị (vì điều này có nghĩa là chúng ta phải có số ký tự trung gian giống hệt nhau).

Vì vậy, chúng tôi sử dụng từ điển để lưu trữ các giá trị trước đó cho biểu đồ.

Python thực hiện:

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")) 

Nếu bạn đã có một bảng chữ cái lớn hơn, bạn có thể sử dụng một kỹ thuật tương tự chỉ lưu trữ một giá trị băm thay vì toàn bộ biểu đồ. Ví dụ, bạn có thể chỉ cần chọn một mã ngẫu nhiên cho mỗi ký tự và thêm vào mã cho mỗi chữ cái trong seq, hoặc trừ cho các chữ cái trong seq2.

Bạn sẽ cần thẻ thứ hai để kiểm tra xem các kết quả được đề xuất có chính xác không trong trường hợp xảy ra xung đột băm.

Answer 3

Đó chắc chắn không phải là thuật toán tối ưu nhưng không ai cung cấp một giải pháp đầy đủ chức năng nhưng vì vậy đây là một cách tiếp cận đơn giản:

def sort_possible_substrings(p_str): 
    """The function iterates through every possible substring of p_str and 
    sorts the characters within the substring and finally inserts them in 
    a set which will be returned.""" 

    S = set() 
    # the possible length of the substrings of p_str 
    for s_len in range(1, len(p_str)+1): 
     # the substrings of p_str with s_len length 
     for s in range(len(p_str)-(s_len-1)): 
      sorted_substr = ''.join(sorted(p_str[s:s+s_len])) 
      S.add(sorted_substr) 
    return S 


def longest_common_perm_len(str1, str2): 
    """Build up a set from the substrings of the shorter string with the help of 
    sort_possible_substrings. Iterate through the possible substrings of the 
    longer string from the longest to the shortest and check whether the same 
    string is contained by "candidates" thus by the shorter string.""" 
    shorter, longer = (str1,str2) if len(str1) <= len(str2) else (str2,str1) 
    candidates = sort_possible_substrings(shorter) 
    for win_len in range(len(shorter),0,-1): 
     for s in range(len(longer)-(win_len-1)): 
      str_chunk = ''.join(sorted(longer[s:s+win_len])) 
      if str_chunk in candidates: 
       return win_len 
    return 0 

(Các phân loại của các nhân vật trong chuỗi con có thể được thay thế bằng "biểu đồ" giải pháp của . Peter de Rivaz)

không tối ưu, thuật toán đơn giản này cho phép:

lsubstr.longest_common_perm_len("ABCDZZEFG", "XDBCAXFEG") -> 4 
lsubstr.longest_common_perm_len("ABCD", "XDXACXB") -> 1