Gegeben zwei Strings, finden Sie die längste gemeinsame Tasche von Zeichen

Question

Diese Frage unterscheidet sich etwas von der Art der längsten Sequenz oder Teilstring aus zwei Strings zu finden.

Bei zwei Strings der gleichen Größe N, finden Sie die längsten Teilstrings aus jeder Zeichenkette, so dass die Teilstrings die gleiche Tüte Zeichen enthalten.

Die beiden Teilstrings müssen nicht unbedingt dieselbe Sequenz haben. Aber sie müssen die gleiche Tüte Chars haben.

Zum Beispiel

a = ABCDDEGF b = FPCDBDAX

die längste passende Tasche der Zeichen sind ABCDD (ABCDD aus einem, aus CDBDA b)

Wie dieses Problem zu lösen?

---

UPDATE

Das Ziel ist Substrings von jeder Eingabekette zu finden, so dass sie die gleiche Tasche von Zeichen haben. Wenn sie "Teilzeichenfolge" sagen, müssen sie aufeinanderfolgende Zeichen sein.

---

aktualisieren: Anfangs dachte ich, einen dynamischen Programmieransatz. Es funktioniert wie folgt.

Um zwei Beutel mit Zeichen der gleichen Länge K zu vergleichen, würde es O (K) Zeit benötigen, um dies zu erreichen. Konvertieren jede Zeichenfolge in eine Verkürzen Form:

ABCDDEGF -> A1B1C1D2E1G1F1 
FPCDBDAX -> A1B1C1D2F1P1X1 

Das Verkürzen Form sortiert Alphabete nach der Anzahl der Frequenzen in der Zeichenfolge folgt. Das Konstruieren, Sortieren und Vergleichen der verkürzten Formen würde O (K) -Zeit insgesamt benötigen. (Die Implementierung kann jedoch unter Verwendung eines Arrays von Zeichen erreicht werden.)

Zwei Beutel mit Zeichen sind gleich, wenn ihre verkürzten Formen die gleichen Zeichen und die entsprechenden Häufigkeiten haben.

Zusätzlich braucht es O (logK) Zeit, um die Differenzzeichen zwischen den beiden Strings zu finden.

nun für zwei Eingänge Strings:

1. Wenn ihre shorten Formen identisch sind, dann ist dies die längste gemeinsame Tasche von Zeichen.
2. Suchen Sie Zeichen in String1 so, dass sie nicht in String2 erscheinen. Tokenize string1 in mehrere Teilstrings basierend auf diesen Zeichen.
3. Suchen Sie Zeichen in String2, sodass sie nicht in Zeichenfolge1 angezeigt werden. Tokenize string2 in mehrere Teilstrings basierend auf diesen Zeichen.
4. Jetzt haben wir zwei Liste von Zeichenfolgen. Vergleichen Sie jedes Paar (was wiederum das gleiche Problem mit einer kleineren Eingabegröße ist) und finden Sie den längsten gemeinsamen Beutel mit Zeichen.

Der schlimmste Fall wäre O (N) sein, und am besten Fall würde O (N) sein. Irgendeine bessere Idee?

Answer 1

Erstellen Sie einen Satz der Zeichen, die in a vorhanden sind, und ein anderes der in b vorhandenen Zeichen. Gehen Sie durch jede Saite und schlagen Sie alle Zeichen, die nicht in der Menge enthalten sind, aus der anderen Saite an (z. B. überschreiben Sie sie mit einem ansonsten unmöglichen Wert). Finde die längste Zeichenfolge, die in jedem übrig bleibt (d. H. Die längste Kette von nur "nicht-gezogenen" Zeichen).

Edit: Hier ist eine Lösung, die oben in etwa wie angegeben funktioniert, aber in einer eher sprachspezifische Art und Weise (unter Verwendung von C++ locales/Facetten):

#include <string> 
#include <vector> 
#include <iostream> 
#include <locale> 
#include <sstream> 
#include <memory> 

struct filter : std::ctype<char> { 
    filter(std::string const &a) : std::ctype<char>(table, false) { 
     std::fill_n(table, std::ctype<char>::table_size, std::ctype_base::space); 

     for (size_t i=0; i<a.size(); i++) 
      table[(unsigned char)a[i]] = std::ctype_base::upper; 
    } 
private: 
    std::ctype_base::mask table[std::ctype<char>::table_size]; 
}; 

std::string get_longest(std::string const &input, std::string const &f) { 
    std::istringstream in(input); 
    filter *filt = new filter(f); 

    in.imbue(std::locale(std::locale(), filt)); 

    std::string temp, longest; 

    while (in >> temp) 
     if (temp.size() > longest.size()) 
      longest = temp; 
    delete filt; 
    return longest; 
} 

int main() { 
    std::string a = "ABCDDEGF", b = "FPCDBDAX"; 
    std::cout << "A longest: " << get_longest(a, b) << "\n"; 
    std::cout << "B longest: " << get_longest(b, a) << "\n"; 
    return 0; 
} 

Edit2: Ich glaube, diese Implementierung O (N) in allen Fällen (eine Überquerung jeder Saite). Das basiert auf std::ctype<char>, das eine Tabelle für Nachschlagevorgänge verwendet, die O (1) ist. Mit einer Hash-Tabelle würde Lookups auch O (1) erwartete Komplexität, sondern O (N) im ungünstigsten Fall, so Gesamtkomplexität wäre O (N) erwartet, aber O (N) im schlechtesten Fall. Mit einem Set basierend auf einem ausgeglichenen Baum erhält man insgesamt O (N lg N).

Answer 2

Hier ist meine eher anti-pythonic Implementierung, die dennoch in den Sätzen und Strings Pythons wunderbare gebaut nutzt.

a = 'ABCDDEGF' 
b = 'FPCDBDAX' 

best_solution = None 
best_solution_total_length = 0 

def try_expand(a, b, a_loc, b_loc): 
    # out of range checks 
    if a_loc[0] < 0 or b_loc[0] < 0: 
     return 
    if a_loc[1] == len(a) or b_loc[1] == len(b): 
     return 


    if set(a[a_loc[0] : a_loc[1]]) == set(b[b_loc[0] : b_loc[1]]): 
     global best_solution_total_length, best_solution 
     #is this solution better than anything before it? 
     if (len(a[a_loc[0] : a_loc[1]]) + len(b[b_loc[0] : b_loc[1]])) > best_solution_total_length: 
      best_solution = (a_loc, b_loc) 
      best_solution_total_length = len(a[a_loc[0] : a_loc[1]]) + len(b[b_loc[0] : b_loc[1]]) 


    try_expand(a, b, (a_loc[0]-1, a_loc[1]), (b_loc[0], b_loc[1])) 
    try_expand(a, b, (a_loc[0], a_loc[1]+1), (b_loc[0], b_loc[1])) 
    try_expand(a, b, (a_loc[0], a_loc[1]), (b_loc[0]-1, b_loc[1])) 
    try_expand(a, b, (a_loc[0], a_loc[1]), (b_loc[0], b_loc[1]+1)) 


for a_i in range(len(a)): 
    for b_i in range(len(b)): 
     # starts of the recursive expansion from identical letters in two substrings 
     if a[a_i] == b[b_i]: 
      # if substrings were expanded from this range before then there won't be an answer there 
      if best_solution == None or best_solution[0][0] > a_i or best_solution[0][1] <= a_i or best_solution[1][0] > b_i or best_solution[1][1] <= b_i: 
        try_expand(a, b, (a_i, a_i), (b_i, b_i)) 


print a[best_solution[0][0] : best_solution[0][1]], b[best_solution[1][0] : best_solution[1][1]] 

vergessen zu erwähnen, dass dies offensichtlich ein ziemlich Brute-Force-Ansatz ist, und ich bin sicher, dass ein Algorithmus gibt es die viel läuft, viel schneller.

Answer 3

Nur eine Notiz zu sagen, dass dieses Problem eine „gierig“ Lösung, bei der nacheinander größere Beutel ausgebildet sind, durch die Erweiterung bestehender machbar Taschen ein Element zu einem Zeitpunkt nicht zugeben. Der Grund ist, dass selbst wenn ein längen k machbar Beutel vorhanden ist, es nicht machbar Beutel der Länge zu sein braucht (k-1), wie die folgende Gegenbeispiel zeigt:

ABCD 
CDAB 

Offensichtlich gibt es eine Länge-4 bag (A:1, B:1, C:1, D:1) geteilt durch die zwei Saiten, aber es gibt keine geteilte Länge-3 Tasche. Dies deutet darauf hin, dass das Problem ziemlich schwierig sein könnte.

Answer 4

lassen Sie sich dieses Problem wie folgt .. diese Lösung wird zu mehr optimiert und wird sehr einfach zu programmieren, aber lesen Sie durch die def und Sie MUSS lesen Sie den Code, um die Idee zu bekommen ... sonst wird es nur verrückt klingen und komplexe

üBER dIESE

in Ihre Fragen denke, die 2 Beispiel Saiten gaben Sie können sie als zwei Satz nehmen, das heißt {x, y, z}, von Zeichen ...

UND .. UND ...Ihr resultierendes substring (Set) wird ein mit Zeichen gemeinsam in beiden Strings (Sets) und wird kontinuierliche Einträge und die Qualifikation Teilzeichenfolge (ser) wird ein mit höchster Anzahl von Einträgen

oben sein sind einige Eigenschaften des Ergebnisses, sondern nur dann, wenn über den folgenden Algorithmus \ Methodik verwendet arbeiten

wir zwei Sätze

a = {} BAHYJIKLO

habenb = {YTSHYJLOP}

Nehmen

a U b = {-, -, H, Y, J, -, -, L, O}

b U a = {Y, -, -, H, Y, J, L, O, -}

seine nur, dass ich habe ersetzt die Charaktere, die nicht für die Vereinigung zu qualifizieren hat gesetzt mit einem "-" oder jede spezielle \ ignoriert Charakter

Dabei haben wir zwei Saiten, aus denen wir leicht HYJ extrahieren kann, LO, Y, HYJLO

jetzt Zeichenfolge \ Substrings Vergleiche und unterschiedliche Verarbeitung braucht Zeit so, was ich tun ist, ich diese schreiben strings \ substrings zu einer Textdatei mit Leerzeichen oder anderen Zeilen getrennt .. so dass ich beim Lesen einer Datei den ganzen String anstelle einer geschachtelten Schleife bekomme, um einen Teilstring zu finden oder temporäre Variablen zu verwalten ....

nachdem Sie HYJ, LO,haben, HYJLO Ich denke, die kein Problem das gewünschte Ergebnis zu finden ....

HINWEIS: wenn Sie zuerst eine Unter machen die Verarbeitung die Zeichenkette und Unterketten in diesem mit temporären Variablen und verschachtelten Schleifen starten String dann suchen sie ... dann sein gehen sehr teure Lösung zu sein ... Sie haben so zu verwenden, die Einreichung ...

char a[20], b[20]; //a[20] & b[30] are two strings 
cin>>a; cin>>b; 
int t=0; 

open a temporary text file "file1" to write '(built-in-function works here)' 
//a U b 
for(int x=0; x<length(a); x++) 
{ 
    t=0; 

    for(int y=0; y<length(b); x++) 
     { if(a[x] == b[y]) t=1; } 

    if(t == 1) 
     { 
      write 'a[x]' to the file1 '(built-in-function works here)' 
      t=0; 
     } 
    else 
     write a 'space' to the file1 '(built-in-function works here)' 
} 

//b U a 
for(int x=0; x<length(a); x++) 
{ 
    t=0; 

    for(int y=0; y<length(b); x++) 
     { if(b[x] == a[y]) t=1; } 

    if(t == 1) 
     { 
     write 'a[x]' to the file1 '(built-in-function works here)' 
     t=0; 
     } 
    else 
     write a 'space' to the file1 '(built-in-function works here)' 
} 
/*output in the file wil be like this 
_____FILE1.txt_____ 
    HYJ LO Y HYJLO   
*/ 
//load all words in an array of stings from file '(built-in-function works here)' 

char *words[]={"HYJ","LO","Y","HYJLO"}; 
int size=0,index=0; 

for(int x=0; x<length(words); x++) 
    for(int y=0; x<length(words); y++) 
    { 
     if(x!=y && words[x] is a substring of words[y]) // '(built-in-function works here)' 
      { 
       if(length(words[x]) < size) 
       { 
        size = length(words[x]; 
        index = x; 
       } 
      } 
    } 

cout<< words[x]; 
//its the desired result.. its pretty old school bu i think you get the idea 

} 

i schrieb den Code für ... seine Arbeit, wenn Sie es wollen Gib mir E-Mail Ich werde es Ihnen senden ... BTW Ich mag dieses Problem und die Komplexität dieses Algo ist 3n (Quadrat)