Längste nicht unterlaufende Teilzeichenfolge in C++

Question

Ich versuche, die längste Teilzeichenfolge ohne wiederholte Zeichen zu finden. Ich habe einen booleschen Vektor, um die 256 Ascii-Zeichen zu verfolgen.

#include <iostream> 
#include <cstdio> 
#include <string> 
#include <algorithm> 

using namespace std; 

int main() 
{ 
    string s = "aaaaaaaaaaaaasadfrhtytbgrbrsvsrhvsg"; 
    vector<bool> v(256, false); 
    int j = 0, len = 0, index = 0; 

    for(int i = 0; i < s.length(); i++) 
    { 
     if(!v[s[i]]) 
     { 
      j++; 

      if(j > len) 
      { 
       len = j; 
       index = i - j; 
      } 

      v[s[i]] = true; 
     } 
     else 
     { 
      j = 0; 
      v.clear(); 
     } 
    } 

    cout << s.substr(index, len) + " " << len << endl; 
} 

kann ich verstehen, warum es die Ausgabe adfrht 6 gibt, whreas die korrekte Ausgabe 8. sadfrhty ist

Answer 1

Der Grund, warum Sie das falsche Ergebnis ist immer ist, weil der grundlegende Ansatz ist ein wenig beweglichen Teile fehlen . Sie verfolgen nicht alle Informationen, die Sie benötigen, um dies zu berechnen. Nicht nur müssen Sie verfolgen, welche Zeichen Sie gesehen haben, sondern auch an welcher Position in der Zeichenfolge, in der sie gesehen wurden (ich nehme an, dass Sie dies bei O (n) Komplexität halten möchten).

Auf diese Weise müssen Sie, wenn Sie ein zuvor gefundenes Zeichen sehen, den Zähler "aufeinanderfolgende, nicht wiederholte Zeichen bis jetzt" zurücksetzen, um nach das vorherige Auftreten des gleichen Zeichens, das Sie suchen, zu beginnen an, in der aktuellen Position. Außerdem werden alle bisher gesehenen Charaktere nicht mehr gesehen, denn wenn du eine Sekunde darüber nachdenkst, sollte es für dich einen Sinn ergeben.

Das ist das fehlende Teil Ihrer Implementierung. Außerdem verfolgt es nicht die Position der längsten Saite, ganz richtig.

Folgendes sollte die von Ihnen gesuchten Ergebnisse liefern.

uns wissen lassen, was Grad Sie :-) für Ihre Hausaufgabe erhielt

#include <iostream> 
#include <cstdio> 
#include <string> 
#include <algorithm> 
#include <vector> 

using namespace std; 

int main() 
{ 
    string s = "aaaaaaaaaaaaasadfrhtytbgrbrsvsrhvsg"; 
    vector<bool> v(256,false); 
    vector<int> seen_at(256); 

    int longest_starting_pos=0, longest_length=0; 

    int current_length=0; 

    for (int i=0; i<s.length(); i++) 
    { 
     if (v[s[i]]) 
     { 
      for (int j=i-current_length; j<seen_at[s[i]]; ++j) 
       v[s[j]]=false; 
      current_length=i-seen_at[s[i]]-1; 
     } 

     v[s[i]]=true; 
     seen_at[s[i]]=i; 
     if (++current_length > longest_length) 
     { 
      longest_length=current_length; 
      longest_starting_pos=i-current_length+1; 
     } 
    } 

    cout<<s.substr(longest_starting_pos, longest_length)+" "<<longest_length<<endl; 
} 

Answer 2

Ihr Algorithmus ist nicht korrekt. Was ist falsch mit Ihrem Algorithmus ist, dass, sobald es ein Zeichen überprüft, es nicht zurück zu diesem Zeichen, um es erneut zu überprüfen, wenn die Teilzeichenfolge einschließlich dieses Zeichen nicht am längsten sein. Die erste s wird in der Zeichenfolge der Länge 2 überprüft, die as ist, aber wenn die nächste a gefunden wird, wird die s vergessen, obwohl es die nächste Teilzeichenfolge länger machen könnte. Versuchen Sie diesen Code:

#include <iostream> 
#include <cstdio> 
#include <string> 
#include <algorithm> 
#include <vector> 

using namespace std; 

int main() 
{ 
    string s = "aaaaaaaaaaaaasadfrhtytbgrbrsvsrhvsg"; 
    vector<bool> v(256,false); 
    int longStart = 0; 
    int longEnd = 0; 
    int start = 0 

    for (end = 0; end < s.length(); end++) 
    { 
     if (!v[s[end]]) // if character not already in the substring 
     { 
      v[s[end]] = true; 

      if (end - start > longEnd - longStart) 
      { 
       longEnd = end; 
       longStart = start; 
      } 
     } 
     else //the character is already in the substring, so increment the 
       //start of the substring until that character is no longer in it 
     { 
      //get to the conflicting character, but don't get to the new character 
      while ((s[start] != s[end]) && (start < end)) 
      { 
       start++; 
       v[s[start]] = false; 
      } 

      //remove the conflicting character 
      start++; 
      //don't set v[s[start]] to false because that character is still 
      //encountered, but as the newly appended character, not the first 
     } 
    } 

    longEnd++; //make longEnd the index after the last character for substring purposes 
    cout << s.substr(longStart, longEnd - longStart) + " " << (longEnd - longStart) << endl; 
} 

Im Grunde, was dieser Code tut, ist es eine laufende Teilzeichenfolge hält, und immer dann, wenn es ein Zeichen trifft, die bereits in der Teilkette ist, erhöht er den Start der Teilkette bis zu diesem neuen Charakter ist nicht mehr in der Teilzeichenfolge wird dann normal fortgesetzt. Es prüft auch jedes Mal, wenn das Ende inkrementiert wird, wenn dieser Teilstring länger als der bisher längste ist. Das ist O (n) ich glaube, wie du wolltest.

Verteilen Sie auch Ihren Code. Kurzer Code bedeutet nichts, wenn Sie ihn nicht lesen und leicht debuggen können. Wenn Sie Probleme mit Ihrem Code haben, sollten Sie alles manuell ausführen, um besser zu verstehen, wie alles funktioniert und was passiert.

Hoffe, das hilft!