Серия соответствия подстроки независимо от порядка символов

Question

я не мог найти ответ на следующий гипотетический вопрос интервью:

Учитывая два строковых последовательностей длины N, как вы можете найти максимальную длину совпадающих подстрок, независимо от того, ,

Например, учитывая seq1 = "ABCDEFG" и seq2 = "DBCAPFG", максимальная длина окна 4. (ABCD от seq1 и DBCA от seq2).

Answer 1

Asumptions

Для заданных массивов 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] были s orted (возможно, построить двоичное дерево P), тогда поиск A [i] в ​​B [0..j] будет O (log n), и весь алгоритм будет O (n log n)

Помогите проверить это было бы замечательно.
Какие-либо контрпримеры?

Answer 2

Здесь находится решение 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 3

Это, конечно, не оптимальный алгоритм, но никто не предоставил полностью функциональное решение еще так вот простой подход:

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 

(Сортировка символов внутри подстроки можно заменить раствором «Гистограмма» из . Питер де Рива)

Это не является оптимальным, простой алгоритм дает:

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