Finden gebräuchlichste Paar von Zeichen in einer Zeichenkette

Question

i die folgende Funktion

//O(n^2) 
void MostCommonPair(char * cArr , char * ch1 , char * ch2 , int * amount) 
{ 
    int count , max = 0; 
    char cCurrent , cCurrent2; 
    int i = 0 , j; 
    while(*(cArr + i + 1) != '\0') 
    { 
     cCurrent = *(cArr + i); 
     cCurrent2 = *(cArr + i + 1); 
     for(j = i , count = 0 ; *(cArr + j + 1) != '\0' ; j++) 
     { 
      if(cCurrent == *(cArr + j) && cCurrent2 == *(cArr + j + 1)) 
      { 
       count++; 
      } 
     } 
     if(count > max) 
     { 
      *ch1 = cCurrent; 
      *ch2 = cCurrent2; 
      max = *amount = count; 
     } 
     i++; 
    } 
} 

für folgende Eingabe

"xdshahaalohalobscxbsbsbs"

ch1 = b ch2 = s amount = 4

geschrieben

aber meiner Meinung nach ist die Funktion sehr uneffizient, gibt es eine Möglichkeit, die Zeichenkette nur einmal zu durchlaufen oder die Laufgröße auf O (n) zu reduzieren?

Answer 1

Da char bis zu 256 Werte enthalten kann, können Sie eine zweidimensionale Tabelle mit [256 * 256] Leistungsindikatoren einrichten, indem Sie die Zeichenfolge einmal durchlaufen und den Zähler für jedes Zeichenpaar in der Zeichenfolge erhöhen. Dann können Sie durch die Tabelle der 256x256 Zahlen gehen, die größte Anzahl auswählen und wissen, zu welchem ​​Paar es gehört, indem Sie auf seine Position im 2D-Array schauen. Da die Größe der Zählertabelle unabhängig von der Länge der Zeichenfolge auf einen konstanten Wert festgelegt ist, lautet diese Operation O(1), obwohl zwei verschachtelte Schleifen erforderlich sind.

int count[256][256]; 
memset(count, 0, sizeof(count)); 
const char *str = "xdshahaalohalobscxbsbsbs"; 
for (const char *p = str ; *(p+1) ; p++) { 
    count[(int)*p][(int)*(p+1)]++; 
} 
int bestA = 0, bestB = 0; 
for (int i = 0 ; i != 256 ; i++) { 
    for (int j = 0 ; j != 256 ; j++) { 
     if (count[i][j] > count[bestA][bestB]) { 
      bestA = i; 
      bestB = j; 
     } 
    } 
} 
printf("'%c%c' : %d times\n", bestA, bestB, count[bestA][bestB]); 

Hier ist ein link to a demo on ideone.

Beachten Sie, dass, obwohl dies ist die schnellstmögliche Lösung asymptotisch (das heißt, es ist O(N), und man kann es nicht schneller als O(N)) die Leistung für kürzere Saiten nicht gut sein. In der Tat wird Ihre Lösung bei Eingaben, die kürzer als etwa 256 Zeichen sind, vermutlich sogar noch mehr schlagen. Es gibt eine Reihe von Optimierungen, die Sie auf diesen Code anwenden können, aber ich habe mich dagegen entschieden, sie hinzuzufügen, um die Grundidee des Codes in seiner reinsten und einfachsten Form klar sichtbar zu machen.

Answer 2

Ja, Sie können dies in ungefähr linearer Zeit tun, indem Sie eine laufende Zählung beibehalten.

Hilft das?

Answer 3

von den meisten „gemeinsames Paar“ Angenommen, du meinst die häufigste Satz von zwei aufeinanderfolgenden Zeichen

---

Bei Pseudo-Code-Ebene Sie

Read the first character into the "second character" register 
while(there is data) 
    store the old second character as the new first character 
    read the next character as the second one 
    increment the count associated with this pair 
Select the most common pair 

So wollen, was Sie brauchen, ist ein leistungsfähiges Algorithmus zum Speichern und Zählen von Zeichenpaaren und Finden der gebräuchlichsten Zeichen.

Answer 4

Wenn Sie O (n) Laufzeit können Sie ein hashtable verwenden (zum Beispiel Java HashMap)

• Iterate durch die Zeichenfolge genau einmal, 1 Zeichen in einer Zeit O (n)
• Für jedes Zeichen besuchten, nach vorne schaut um genau 1 mehr Charakter (Dies ist also dein Charakter Paar - sie einfach verketten) O (1)
• Für jeden solchen Charac ter Paar gefunden, zuerst sucht es in der Hash-Tabelle: O (1)
  • Wenn es noch nicht in der Hash-Tabelle, mit dem Zeichenpaar als Schlüssel, und int 1 als Wert hinzufügen in (dies zählt die wie oft Sie es in der Zeichenfolge gesehen haben). O (1)
  • Wenn es bereits in der Hash-Tabelle ist, erhöht seinen Wert O (1)
• Nachdem Sie durch die Zeichenfolge getan suchen, überprüfen Sie die Hash-Tabelle für das Paar mit der höchsten Zählung . O (m) (wobei m die Anzahl der möglichen Paarungen ist; notwendigerweise)