All-but-One-Übereinstimmungen finden

18

Bei dieser Herausforderung geht es darum, Code zu schreiben, um das folgende Problem zu lösen.

Bei zwei Zeichenfolgen A und B sollte Ihr Code den Start- und den Endindex einer Teilzeichenfolge von A mit den folgenden Eigenschaften ausgeben.

  • Die Teilzeichenfolge von A sollte auch mit einigen Teilzeichenfolgen von B mit bis zu einer Ersetzung eines einzelnen Zeichens in der Zeichenfolge übereinstimmen.
  • Es sollte keine Teilzeichenfolge von A mehr geben, die die erste Eigenschaft erfüllt.

Beispielsweise:

A = xxxappleyyyyyyy

B = zapllezzz

Die Teilzeichenfolge applemit Indizes 4 8(Indizierung von 1) wäre eine gültige Ausgabe.

Ergebnis

Die Punktzahl Ihrer Antwort ergibt sich aus der Summe der Länge Ihres Codes in Byte und der Zeit in Sekunden, die auf meinem Computer benötigt wird, wenn Zeichenfolgen A und B mit einer Länge von jeweils 1 Million ausgeführt werden.

Testen und Eingeben

Ich werde Ihren Code mit zwei Zeichenfolgen mit einer Länge von 1 Million ausführen, die den Zeichenfolgen in http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/ entnommen wurden.

Die Eingabe erfolgt standardmäßig in zwei Zeichenfolgen, die durch eine neue Zeile getrennt werden.

Sprachen und Bibliotheken

Sie können jede Sprache verwenden, die über einen frei verfügbaren Compiler / Interpreter / etc. Verfügt. für Linux und alle Bibliotheken, die auch Open Source sind und für Linux frei verfügbar sind.

Mein Computer Die Timings werden auf meinem Computer ausgeführt. Dies ist eine Ubuntu-Standardinstallation auf einem AMD FX-8350 Eight-Core-Prozessor. Dies bedeutet auch, dass ich in der Lage sein muss, Ihren Code auszuführen. Verwenden Sie daher nur leicht verfügbare kostenlose Software und fügen Sie vollständige Anweisungen zum Kompilieren und Ausführen Ihres Codes bei.

isaacg
quelle
Sie benötigen eine genauere Definition der Punktzahl. Die Laufzeit auf Ihrem Computer klingt nicht nach einer guten Bewertungsmethode.
mbomb007
7
@ mbomb007 Dies ist die einzig sinnvolle Methode zur Messung der Codegeschwindigkeit und wird immer bei schnellsten Codewettbewerben auf PPCG verwendet! Normalerweise posten die Leute ihre Punktzahl in ihrer Antwort auf ihrem eigenen Computer und warten, bis das OP eine endgültige Punktzahl erstellt. Es ist mindestens 100% eindeutig.
5
@ mbomb007 das ist eine sehr weit verbreitete Bewertungsmethode für den schnellsten Code.
Optimierer
if(hash(str1 == test1 && str2 == test2)) print("100,150") else ..-- Gedanken?
John Dvorak
2
@FryAmTheEggman Im sehr unwahrscheinlichen Fall eines Unentschieden gewinnt die erste Antwort. appleybenötigt zwei passende Auswechslungen apllez. Vielleicht hast du verpasst, dass es apllin B ist und nicht appl?

Antworten:

4

C ++ Zeit: O (n ^ 2), zusätzlicher Raum: O (1)

Es dauert 0,2 Sekunden, um die 15-KB-Daten auf meinem Computer zu vervollständigen.

Verwenden Sie zum Kompilieren:

g++ -std=c++11 -O3 code.cpp -o code

Um es auszuführen, benutze:

./code < INPUT_FILE_THAT_CONTAINS_TWO_LINES_SPERATED_BY_A_LINE_BREAK

Erklärung

Die Idee ist einfach, für Zeichenfolge s1und s2wir versuchen zu kompensieren s2durch i:

s1: abcabcabc
s2: bcabcab

Wenn der Versatz 3 ist:

s1: abcabcabc
s2:    bcabcab

Dann iführen wir für jeden Versatz einen dynamischen Programmierungsscan auf s1[i:]und durch s2. Für jeden j, lassen Sie f[j, 0]die maximale Länge sein , dso dass s1[j - d:j] == s2[j - i - d: j - i]. Ebenso sei f[j, 1]die maximale Länge dso bemessen, dass Zeichenketten s1[j - d:j]und s2[j - i - d:j - i]sich höchstens um 1 Zeichen unterscheiden.

Also für s1[j] == s2[j - i], haben wir:

f[j, 0] = f[j - 1, 0] + 1  // concat solution in f[j - 1, 0] and s1[j]
f[j, 1] = f[j - 1, 1] + 1  // concat solution in f[j - 1, 1] and s1[j]

Andernfalls:

f[j, 0] = 0  // the only choice is empty string
f[j, 1] = f[j - 1, 0] + 1  // concat solution in f[j - 1, 0] and s1[j] (or s2[j - i])

Und:

f[-1, 0] = f[-1, 1] = 0 

Da wir nur f [j - 1,:] benötigen, um f [j,:] zu berechnen, wird nur O (1) zusätzlicher Raum verwendet.

Schließlich ist die maximale Länge:

max(f[j, 1] for all valid j and all i)

Code

#include <string>
#include <cassert>
#include <iostream>

using namespace std;

int main() {
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    int n1, n2;
    n1 = s1.size();
    n2 = s2.size();
    int max_len = 0;
    int max_end = -1;
    for(int i = 1 - n2; i < n1; i++) {
        int f0, f1;
        int max_len2 = 0;
        int max_end2 = -1;
        f0 = f1 = 0;
        for(int j = max(i, 0), j_end = min(n1, i + n2); j < j_end; j++) {
            if(s1[j] == s2[j - i]) {
                f0 += 1;
                f1 += 1;
            } else {
                f1 = f0 + 1;
                f0 = 0;
            }
            if(f1 > max_len2) {
                max_len2 = f1;
                max_end2 = j + 1;
            }
        }
        if(max_len2 > max_len) {
            max_len = max_len2;
            max_end = max_end2;
        }
    }
    assert(max_end != -1);
    // cout << max_len << endl;
    cout << max_end - max_len + 1 << " " << max_end << endl;
}
Strahl
quelle
Entschuldigung, ich habe mir den Code angesehen und kann nicht feststellen, wie er die Möglichkeit der Übereinstimmung von Zeichenfolgen mit Ausnahme eines Zeichens berücksichtigt, wie im Beispiel "apple" und "aplle". Könntest du erklären?
Lorlork
@rcrmn Genau das macht der dynamische Programmierteil. Zum besseren Verständnis ist es hilfreich, die Werte für f [j, 0] und f [j, 1] für einige einfache Fälle manuell zu berechnen. Der vorherige Code hat einige Fehler, daher habe ich den Beitrag aktualisiert.
Ray
Danke dafür. Denken Sie, dass es möglicherweise auch eine O (n log n) -Lösung gibt?
2

C ++

Ich habe versucht, mir einen guten Algorithmus zu überlegen, aber ich bin heute etwas abgelenkt und konnte mir nichts vorstellen, was gut funktionieren würde. Dies läuft zur Zeit 0 (n ^ 3), es ist also sehr langsam. Die andere Option, an die ich gedacht habe, hätte theoretisch schneller sein können, hätte aber O (n ^ 2) Platz in Anspruch genommen, und mit Eingaben von 1M wäre sie noch schlimmer gewesen.

Es ist beschämend, es dauert 190 Sekunden für Eingaben von 15K. Ich werde versuchen, es zu verbessern. Bearbeiten: Mehrfachverarbeitung hinzugefügt. Es dauert jetzt 37 Sekunden für die Eingabe von 15 KB in 8 Threads.

#include <string>
#include <vector>
#include <sstream>
#include <chrono>
#include <thread>
#include <atomic>
#undef cin
#undef cout
#include <iostream>

using namespace std;

typedef pair<int, int> range;

int main(int argc, char ** argv)
{
    string a = "xxxappleyyyyyyy";
    string b = "zapllezzz";

    getline(cin, a);
    getline(cin, b);

    range longestA;
    range longestB;

    using namespace std::chrono;

    high_resolution_clock::time_point t1 = high_resolution_clock::now();

    unsigned cores = thread::hardware_concurrency(); cores = cores > 0 ? cores : 1;

    cout << "Processing on " << cores << " cores." << endl;

    atomic<int> processedCount(0);

    vector<thread> threads;

    range* longestAs = new range[cores];
    range* longestBs = new range[cores];
    for (int t = 0; t < cores; ++t)
    {
        threads.push_back(thread([&processedCount, cores, t, &a, &b, &longestBs, &longestAs]()
        {
            int la = a.length();
            int l = la / cores + (t==cores-1? la % cores : 0);
            int lb = b.length();
            int aS = t*(la/cores);

            for (int i = aS; i < aS + l; ++i)
            {
                int count = processedCount.fetch_add(1);
                if ((count+1) * 100 / la > count * 100 / la)
                {
                    cout << (count+1) * 100 / la << "%" << endl;
                }
                for (int j = 0; j < lb; ++j)
                {
                    range currentB = make_pair(j, j);
                    bool letterChanged = false;
                    for (int k = 0; k + j < lb && k + i < la; ++k)
                    {
                        if (a[i + k] == b[j + k])
                        {
                            currentB = make_pair(j, j + k);
                        }
                        else if (!letterChanged)
                        {
                            letterChanged = true;
                            currentB = make_pair(j, j + k);
                        }
                        else
                        {
                            break;
                        }
                    }
                    if (currentB.second - currentB.first > longestBs[t].second - longestBs[t].first)
                    {
                        longestBs[t] = currentB;
                        longestAs[t] = make_pair(i, i + currentB.second - currentB.first);
                    }
                }
            }
        }));
    }

    longestA = make_pair(0,0);
    for(int t = 0; t < cores; ++t)
    {
        threads[t].join();

        if (longestAs[t].second - longestAs[t].first > longestA.second - longestA.first)
        {
            longestA = longestAs[t];
            longestB = longestBs[t];
        }
    }

    high_resolution_clock::time_point t2 = high_resolution_clock::now();

    duration<double> time_span = duration_cast<duration<double>>(t2 - t1);

    cout << "First substring at range (" << longestA.first << ", " << longestA.second << "):" << endl;
    cout << a.substr(longestA.first, longestA.second - longestA.first + 1) << endl;
    cout << "Second substring at range (" << longestB.first << ", " << longestB.second << "):" << endl;
    cout << b.substr(longestB.first, longestB.second - longestB.first + 1) << endl;
    cout << "It took me " << time_span.count() << " seconds for input lengths " << a.length() << " and " << b.length() <<"." << endl;

    char c;
    cin >> c;
    return 0;
}
rorlork
quelle
Es tut mir wirklich leid, dass es eine so schlechte Lösung ist. Ich habe nach einem Algorithmus gesucht, um dies in besserer Zeit zu erreichen, aber im Moment nichts gefunden ...
rorlork
Nun, die Komplexität der erforderlichen Aufgabe sollte zwischen O (n ^ 4) und O (n ^ 5) liegen, so dass lange Laufzeiten eine
Selbstverständlichkeit
Ich glaube, es sollte im schlimmsten Fall eher O (n ^ 3) sein, zumindest bei meinem Algorithmus. Wie auch immer, ich bin sicher, dass etwas getan werden kann, um es zu verbessern, wie eine Art Baumsuche, aber ich bin nicht sicher, wie es implementiert werden würde.
rorlork
Oh ja, O (n ^ 3) es ist ... hatte eine andere Herangehensweise im Sinn, die O (n ^ 4) angenommen hätte, aber diese ist mittlerweile irgendwie nutzlos xD
hoffmale
Sie könnten ein wenig Zeit sparen, wenn Sie das Häkchen in den beiden äußeren for-Schleifen von i < a.length()in ändern i < a.length - (longestA.second - longestA.first)(dasselbe für j und b.length ()), da Sie keine Übereinstimmungen verarbeiten müssen, die kleiner sind als Ihre derzeit längste
hoffmale
2

R

Scheint, als hätte ich das Problem mit der vorherigen Lösung zu kompliziert. Dies ist ungefähr 50% schneller (23 Sek. Auf 15k-Saiten) als die vorherige und ziemlich einfach.

rm(list=ls(all=TRUE))
a="xxxappleyyyyyyy"
b="zapllezzz"
s=proc.time()
matchLen=1
matchIndex=1
indexA = 1
repeat {    
    i = 0
    repeat {
        srch = substring(a,indexA,indexA+matchLen+i)
        if (agrepl(srch,b,max.distance=list(insertions=0,deletions=0,substitutions=1)))
            i = i + 1
        else {
            if (i > 0) {
                matchLen = matchLen + i - 1
                matchIndex = indexA
            }
            break
        }
    }
    indexA=indexA+1
    if (indexA + matchLen > nchar(a)) break
}
c(matchIndex, matchLen + matchIndex)
print (substring(a,matchIndex, matchLen + matchIndex))
print(proc.time()-s)

Dies wird aufgrund der Sprache niemals ein Konkurrent sein, aber ich hatte ein bisschen Spaß dabei.
Ich bin mir der Komplexität nicht sicher, aber über ein paar ~ 15k-Strings dauert es 43 Sekunden, wenn ein einzelner Thread verwendet wird. Der größte Teil davon war das Sortieren der Arrays. Ich habe einige andere Bibliotheken ausprobiert, aber ohne wesentliche Verbesserung.

a="xxxappleyyyyyyy"
b="zapllezzz"
s=proc.time()
N=nchar
S=substring
U=unlist
V=strsplit
A=N(a)
B=N(b)
a=S(a,1:A)
b=S(b,1:B)
a=sort(a,method="quick")
b=sort(b,method="quick")
print(proc.time()-s)
C=D=1
E=X=Y=I=0
repeat{
    if(N(a[C])>E && N(b[D])>E){
        for(i in E:min(N(a[C]),N(b[D]))){
            if (sum(U(V(S(a[C],1,i),''))==U(V(S(b[D],1,i),'')))>i-2){
                F=i
            } else break
        }
        if (F>E) {
            X=A-N(a[C])+1
            Y=X+F-1
            E=F
        }
        if (a[C]<b[D])
            C=C+1
            else
            D=D+1
    } else
        if(S(a[C],1,1)<S(b[D],1,1))C=C+1 else D=D+1
    if(C>A||D>B)break
}
c(X,Y)
print(proc.time()-s)

Methode:

  • Erstellen Sie für jede Zeichenfolge ein Suffix-Array
  • Bestellen Sie die Suffix-Arrays
  • Durchlaufen Sie jedes der Arrays in einer gestaffelten Art und Weise, indem Sie den Anfang jedes Arrays vergleichen
MickyT
quelle
Natürlich ist die einfachste Lösung in R die Verwendung von Bioconductor.
Archaephyrryx
@archaephyrryx Eine Bioleiterlösung würde Spaß machen.
Es wäre ... Aber mein schnelles Lesen der Dokumente ging mir weit über den Kopf. Vielleicht, wenn ich die Bedingungen verstehe :-)
MickyT
Ich habe meinen ersten Kommentar gelöscht. Sie können für diese Herausforderung natürlich jede Open Source-Bibliothek verwenden, die Sie möchten.