Längste gemeinsame Teilzeichenfolge in linearer Zeit

45

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 einer Teilzeichenfolge von B übereinstimmen.
  • Es sollte keine Teilzeichenfolge von A mehr geben, die die erste Eigenschaft erfüllt.

Zum Beispiel:

A = xxxappleyyyyyyy

B = zapplezzz

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

Funktionalität

Sie können davon ausgehen, dass die Eingabe standardmäßig in oder in einer Datei im lokalen Verzeichnis erfolgt. Dies ist Ihre Wahl. Das Dateiformat besteht einfach aus zwei Zeichenfolgen, die durch eine neue Zeile getrennt sind. Die Antwort sollte ein vollständiges Programm sein und nicht nur eine Funktion.

Schließlich möchte ich Ihren Code an zwei Teilzeichenfolgen testen, die den Zeichenfolgen in http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/ entnommen sind .

Ergebnis

Dies ist Code-Golf mit einem Twist. Ihr Code muss rechtzeitig ausgeführt O(n)werden. Dabei nhandelt es sich um die Gesamtlänge der Eingabe.

Sprachen und Bibliotheken

Sie können jede Sprache verwenden, die einen frei verfügbaren Compiler / Interpreter / etc hat. für Linux. Sie sollten nur Standard-Open-Source-Bibliotheken verwenden, die nicht für diese Aufgabe entwickelt wurden. Im Streitfall zähle ich dies als jede Bibliothek, die entweder standardmäßig in Ihrer Sprache enthalten ist oder die Sie von einem Standard-Repository aus auf einem Ubuntu-Standardcomputer installieren können.

Nützliche Informationen

Es gibt mindestens zwei Möglichkeiten, um dieses Problem in linearer Zeit zu lösen. Eine besteht darin, zuerst den Suffix-Baum und die zweite zunächst das Suffix-Array und das LCP-Array zu berechnen.

Gemeinschaft
quelle
4
O(n) timeBist du sicher, dass es möglich ist?
Savenkov Alexey
17
@Lembik Tut mir leid, aber das sind sehr komplexe Algorithmen, und es macht keinen Spaß, mehr als 100 Codezeilen zu sammeln.
FUZxxl
4
Der Artikel unter dem zweiten Link, den Sie unter "Nützliche Informationen" bereitstellen, besagt, dass "das Erstellen [eines Suffixbaums] O (N ^ 2)
-Zeit
3
@Lembik Du solltest einfach die Frage stellen [Schnellster-Code], wo das Programm mit dem besten Worst-Case in Big-Oh-Notation gewinnt. Dann bekommst du wenigstens ein paar Antworten und in dem Moment, in dem jemand es in O (n) lösen kann , werden sie gewinnen.
mbomb007
9
Dies muss die Frage mit den meisten gelöschten Antworten pro gültige Antwort sein ...
FlipTack

Antworten:

39

Python 2, 646 Bytes

G=range;w=raw_input;z=L,m,h=[0]*3
s=w();t=len(s);s+='!%s#'%w();u=len(s);I=z*u
def f(s,n):
 def r(o):
    b=[[]for _ in s];c=[]
    for x in B[:N]:b[s[x+o]]+=x,
    map(c.extend,b);B[:N]=c
 M=N=n--~n/3;t=n%3%2;B=G(n+t);del B[::3];r(2);u=m=p=r(1)>r(0);N-=n/3
 for x in B*1:v=s[x:x+3];m+=u<v;u=v;B[x/3+x%3/2*N]=m
 A=1/M*z or f(B+z,M)+z;B=[x*3for x in A if x<N];J=I[r(0):n];C=G(n)
 for k in C:b=A[t]/N;a=i,j=A[t]%N*3-~b,B[p];q=p<N<(s[i:i-~b],J[i/3+b+N-b*N])>(s[j+t/M:j-~b],J[j/3+b*N]);C[k]=x=a[q];I[x]=k;p+=q;t+=1-q
 return C
S=f(map(ord,s)+z*40,u)
for i in G(u):
 h-=h>0;j=S[I[i]-1]
 while s[i+h]==s[j+h]:h+=1
 if(i<t)==(t<j)<=h>m:m=h;L=min(i,j)
print-~L,L+m

Hierbei wird der in "Simple Linear Work Suffix Array Construction" von Kärkkäinen und Sanders beschriebene Schräglaufalgorithmus verwendet. Die in diesem Artikel enthaltene C ++ - Implementierung fühlt sich bereits ein wenig "golfen" an, aber es gibt noch viel Raum, um sie zu verkürzen. Zum Beispiel können wir rekursiv arbeiten, bis wir zu einem Array der Länge eins kommen, anstatt wie in der Arbeit einen Kurzschluss zu verursachen, ohne die O(n)Anforderung zu verletzen .

Für den LCP-Teil folgte ich "Linear-Time Longest-Common-Prefix-Berechnung in Suffix-Arrays und deren Anwendungen" von Kusai et al.

Das Programm gibt aus, 1 0ob die längste gemeinsame Teilzeichenfolge leer ist.

Hier ist ein Entwicklungscode, der eine frühere Version des Programms enthält, die der C ++ - Implementierung etwas genauer folgt, einige langsamere Vergleichsansätze und einen einfachen Testfallgenerator:

from random import *

def brute(a,b):
    L=R=m=0

    for i in range(len(a)):
        for j in range(i+m+1,len(a)+1):
            if a[i:j] in b:
                m=j-i
                L,R=i,j

    return L+1,R

def suffix_array_slow(s):
    S=[]
    for i in range(len(s)):
        S+=[(s[i:],i)]
    S.sort()
    return [x[1] for x in S]

def slow1(a,b):
    # slow suffix array, slow lcp

    s=a+'!'+b
    S=suffix_array_slow(s)

    L=R=m=0

    for i in range(1,len(S)):
        x=S[i-1]
        y=S[i]
        p=s[x:]+'#'
        q=s[y:]+'$'
        h=0
        while p[h]==q[h]:
            h+=1
        if h>m and len(a)==sorted([x,y,len(a)])[1]:
            m=h
            L=min(x,y)
            R=L+h

    return L+1,R

def verify(a,b,L,R):
    if L<1 or R>len(a) or a[L-1:R] not in b:
        return 0
    LL,RR=brute(a,b)
    return R-L==RR-LL

def rand_string():
    if randint(0,1):
        n=randint(0,8)
    else:
        n=randint(0,24)
    a='zyxwvutsrq'[:randint(1,10)]
    s=''
    for _ in range(n):
        s+=choice(a)
    return s

def stress_test(f):
    numtrials=2000
    for trial in range(numtrials):
        a=rand_string()
        b=rand_string()
        L,R=f(a,b)
        if not verify(a,b,L,R):
            LL,RR=brute(a,b)
            print 'failed on',(a,b)
            print 'expected:',LL,RR
            print 'actual:',L,R
            return
    print 'ok'

def slow2(a,b):
    # slow suffix array, linear lcp

    s=a+'!'+b+'#'
    S=suffix_array_slow(s)

    I=S*1
    for i in range(len(S)):
        I[S[i]]=i

    L=R=m=h=0

    for i in range(len(S)):
        if I[i]:
            j=S[I[i]-1]
            while s[i+h]==s[j+h]:
                h+=1
            if h>m and len(a)==sorted([i,j,len(a)])[1]:
                m=h
                L=min(i,j)
                R=L+h
            h-=h>0

    return L+1,R

def suffix_array(s,K):
    # skew algorithm

    n=len(s)
    s+=[0]*3
    n0=(n+2)/3
    n1=(n+1)/3
    n2=n/3
    n02=n0+n2
    adj=n0-n1

    def radix_pass(a,o,n=n02):
        c=[0]*(K+3)
        for x in a[:n]:
            c[s[x+o]+1]+=1
        for i in range(K+3):
            c[i]+=c[i-1]
        for x in a[:n]:
            j=s[x+o]
            a[c[j]]=x
            c[j]+=1

    A=[x for x in range(n+adj) if x%3]+[0]*3

    radix_pass(A,2)
    radix_pass(A,1)
    radix_pass(A,0)

    B=[0]*n02
    t=m=0

    for x in A[:n02]:
        u=s[x:x+3]
        m+=t<u
        t=u
        B[x/3+x%3/2*n0]=m

    A[:n02]=1/n02*[0]or suffix_array(B,m)
    I=A*1
    for i in range(n02):
        I[A[i]]=i+1

    B=[3*x for x in A if x<n0]
    radix_pass(B,0,n0)

    R=[]

    p=0
    t=adj
    while t<n02:
        x=A[t]
        b=x>=n0
        i=(x-b*n0)*3-~b
        j=B[p]
        if p==n0 or ((s[i:i+2],I[A[t]-n0+1])<(s[j:j+2],I[j/3+n0]) if b else (s[i],I[A[t]+n0])<(s[j],I[j/3])):R+=i,;t+=1
        else:R+=j,;p+=1

    return R+B[p:n0]

def solve(a,b):
    # linear

    s=a+'!'+b+'#'
    S=suffix_array(map(ord,s),128)

    I=S*1
    for i in range(len(S)):
        I[S[i]]=i

    L=R=m=h=0

    for i in range(len(S)):
        if I[i]:
            j=S[I[i]-1]
            while s[i+h]==s[j+h]:
                h+=1
            if h>m and len(a)==sorted([i,j,len(a)])[1]:
                m=h
                L=min(i,j)
                R=L+h
            h-=h>0

    return L+1,R

stress_test(solve)
Mitch Schwartz
quelle
1
Korrigieren Sie mich, wenn ich falsch liege, aber sind das nicht tatsächlich 739 Bytes? Ich habe in mothereff.in/byte-counter kopiert und 2 Leerzeichen aus den Zeilen 6-9 gelöscht, bin mir aber nicht sicher, ob das stimmt.
Patrick Roberts
2
@PatrickRoberts Das sind Registerkarten.
Mitch Schwartz
2
Gute Antwort! Vielleicht möchten Sie einen Blick auf GSACA werfen, eine neuartige lineare Zeit-SACA aus dem Jahr 2016. Die Referenzimplementierung enthält 246 Zeilen voller Kommentare (170 ohne Kommentare) und scheint sehr golfen zu sein. Sie finden es auf Github.
Christoph
1
@MitchSchwartz Ich versuche gerade, auf noPMO zu bleiben, daher kann ich momentan keine starken Emotionen spüren (wahrscheinlich aufgrund von unausgeglichenen Hirnchemikalien). Als ich den Code schnell las, bemerkte mein Syntaxgolfmotor das und ich erinnere mich nicht, irgendwelche spezifischen Emotionen gefühlt zu haben. Hast du dasselbe gedacht oder warum die Frage? :) Jetzt bin ich neugierig.
Yytsi
1
@ TuukkaX Das ist eine interessante Antwort, die ich nicht erwartet hatte. Nun, ich bin mir nicht sicher, ob ich das auf eine spezielle Weise formulieren soll, aber die Tatsache, dass Ihr ursprünglicher Kommentar nicht richtig war, spielte eine Rolle bei der Frage, warum ich mich entschlossen habe. :)
Mitch Schwartz