Longest sottostringa corrispondente indipendentemente l'ordine dei caratteri

Question

non riuscivo a trovare una risposta alla seguente domanda intervista ipotetica:

Date due sequenze di stringa di lunghezza N, come si può trovare la lunghezza massima di sottostringhe corrispondenti a prescindere dalla fine .

Ad esempio, dato seq1 = "ABCDEFG", e seq2 = "DBCAPFG", la finestra lunghezza massima è 4. (ABCD da seq1 e DBCA da seq2).

Answer 1

Asumptions

Per gli array dato A [0..n], B [0..m]

• Finite alfabeto

• non ripetibile caratteri

  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 
  

se B [0..j] erano s orted (forse costruisci l'albero binario P), quindi cerca A [i] in B [0..j] sarebbe O (log n) e l'intero algoritmo sarebbe O (n log n)

Aiutare a convalidare questo sarebbe bello.
Eventuali controesempi?

Answer 2

Ecco una soluzione O (n) (presupponendo dimensioni alfabeto fisse e accesso al dizionario O (1)).

Utilizzare una tabella di frequenza singola che conta per i caratteri in seq1 e in basso per caratteri in seq2. Avremo una finestra corrispondente se questo istogramma prende sempre lo stesso valore (poiché ciò significa che dobbiamo avere un numero identico di caratteri intermedi).

Quindi usiamo un dizionario per memorizzare i valori precedenti per l'istogramma.

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

Se tu avessi un alfabeto più grande è possibile utilizzare una tecnica simile solo la memorizzazione di un valore di hash invece della piena istogramma. Ad esempio potresti semplicemente scegliere un codice casuale per ogni carattere e aggiungere il codice per ogni lettera in seq, o sottrarre le lettere in seq2.

È necessario un secondo passaggio per verificare che le corrispondenze proposte siano corrette in caso di collisione dell'hash.

Answer 3

Non è certamente l'algoritmo ottimale, ma nessuno realizzata una soluzione completamente funzionale ma ecco un approccio semplice:

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 

(L'ordinamento dei caratteri tra sottostringhe potrebbe essere sostituito con la soluzione "istogramma" di . Peter de Rivaz)

Questo non ottimale, l'algoritmo semplice dà:

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