Algo, um die Anzahl der gemeinsamen Zeichen in 2 Strings zu finden [duplizieren] - c, string, algorithm

Ich schreibe ein c-Programm, um die Anzahl der gemeinsamen Zeichen in zwei Strings zu finden.

ZB: aabbccc aabc Ans: 4

   aabcA     aa       Ans:2

(Strings haben Großbuchstaben, Kleinbuchstaben und Zahlen)

Ich habe zwei Algorithmen im Kopf

Angenommen die Länge der Strings ist n, m

1. Sortieren Sie die Arrays und zählen Sie dann die Komplexität von O (nlogn + mlogm)

2.Scan durch zwei Strings und verwenden Sie eine Anzahl Arrays - O (n + m) Komplexität

Kann jemand bitte weitere Optimierung oder andere Methoden vorschlagen, dies zu tun?

Antworten:

im Grunde fragen Sie nach einem Tasche (Multiset) Schnittpunkt.

und ich denke, dass es keinen effizienteren Algo als O (n + m) geben wird, weil du jedes einzelne Element von zwei Taschen mindestens einmal durchlaufen musst.

Da Optimierung für große Eingabe benötigt wird, Idenke, deine zweite Methode ist ziemlich gut (Array-Methode zählen). Unabhängig von dem Algorithmus, den Sie herausfinden wollen, können Sie die Antwort auf Ihr Problem nicht finden, ohne die beiden Strings vollständig zu betrachten. Daher sollte es keine weitere Optimierung für dieses Problem geben, da es bereits O (m + n) ist. Ich denke für kleinere Eingaben wird Ihr erster Algorithmus schneller arbeiten, da eine Konstante von O (26 + 26 + 10) mit Ihrem zweiten Algorithmus verbunden ist. Wenn Sie jedoch an einem schnelleren Code interessiert sind, versuchen Sie, die Methode zum Lesen und Schreiben der Ausgabe zu optimieren. Sie können nach "schnellerem I / O in C ++" googlen und darüber lesen.