Subcadena común más larga en tiempo lineal

45

Este desafío se trata de escribir código para resolver el siguiente problema.

Dadas dos cadenas A y B, su código debería generar los índices de inicio y finalización de una subcadena de A con las siguientes propiedades.

  • La subcadena de A también debe coincidir con alguna subcadena de B.
  • Ya no debería haber una subcadena de A que satisfaga la primera propiedad.

Por ejemplo:

A = xxxappleyyyyyyy

B = zapplezzz

La subcadena applecon índices 4 8(indexación desde 1) sería una salida válida.

Funcionalidad

Puede suponer que la entrada estará en el estándar o en un archivo en el directorio local, esa es su elección. El formato del archivo será simplemente dos cadenas, separadas por una nueva línea. La respuesta debe ser un programa completo y no solo una función.

Eventualmente me gustaría probar su código en dos subcadenas tomadas de las cadenas en http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/ .

Puntuación

Este es el código de golf con un toque diferente. Su código debe ejecutarse a O(n)tiempo, donde nes la longitud total de la entrada.

Idiomas y bibliotecas

Puede usar cualquier idioma que tenga un compilador / intérprete / etc. para Linux Solo debe usar bibliotecas de código abierto estándar no diseñadas para resolver esta tarea. En caso de disputa, contaré esto como cualquier biblioteca que viene como estándar con su idioma o una que puede instalar en una máquina ubuntu predeterminada desde un repositorio predeterminado.

Información útil

Hay al menos dos formas de resolver este problema en tiempo lineal. Una es calcular primero el árbol de sufijos y la segunda es calcular primero la matriz de sufijos y la matriz LCP.

Comunidad
fuente
44
O(n) time¿Estás seguro de que es posible?
Savenkov Alexey
17
@Lembik Lo siento, pero estos son algoritmos muy complejos y no es realmente divertido obtener más de 100 líneas de código.
FUZxxl
44
El artículo en el segundo enlace que proporciona bajo "Información útil" dice que "la construcción [un árbol de sufijos] requiere tiempo O (N ^ 2)"
KSFT
3
@Lembik Deberías hacer la pregunta [código más rápido], donde gana el programa con el mejor peor de los casos en notación big-oh. Entonces al menos obtendrás algunas respuestas, y en el caso de que alguien pueda resolverlo en O (n), ganarán.
mbomb007
99
Esta debe ser la pregunta con la mayoría de las respuestas eliminadas por respuesta válida ...
FlipTack

Respuestas:

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

Utiliza el algoritmo de inclinación descrito en "Construcción de matriz de sufijo de trabajo lineal simple" de Kärkkäinen y Sanders. La implementación de C ++ incluida en ese documento ya se siente un poco "golf", pero todavía hay mucho espacio para acortarla. Por ejemplo, podemos recurrir hasta llegar a una matriz de longitud uno, en lugar de cortocircuito como en el documento, sin violar el O(n)requisito.

Para la parte de LCP, seguí "Cálculo de prefijo común más largo de tiempo lineal en matrices de sufijos y sus aplicaciones" por Kusai et al.

El programa emite 1 0si la subcadena común más larga está vacía.

Aquí hay un código de desarrollo que incluye una versión anterior del programa que sigue la implementación de C ++ un poco más de cerca, algunos enfoques más lentos para la comparación y un simple generador de casos de prueba:

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
fuente
1
Corrígeme si me equivoco, pero ¿no es esto realmente 739 bytes? Copié en mothereff.in/byte-counter y eliminé 2 espacios de las líneas 6-9, pero no estoy seguro de si eso es correcto.
Patrick Roberts el
2
@PatrickRoberts Esas son pestañas.
Mitch Schwartz
2
¡Buena respuesta! Es posible que desee echar un vistazo a GSACA, un novedoso tiempo lineal SACA de 2016. La implementación de referencia tiene 246 líneas llenas de comentarios (170 sin comentarios) y parece muy golfable. Lo encontrarás en github.
Christoph
1
@MitchSchwartz Actualmente estoy tratando de mantenerme en noPMO, por lo que no puedo sentir emociones fuertes en este momento (probablemente debido a los desequilibrios químicos del cerebro). Al momento de leer el código rápidamente, mi motor de golf de sintaxis lo notó y no recuerdo haber sentido ninguna emoción específica. ¿Pensaste en lo mismo o por qué la pregunta? :) Ahora estoy curioso.
Yytsi
1
@ TuukkaX Esa es una respuesta interesante que no esperaba. Bueno, no estoy seguro de si debería estar redactando esto de alguna manera especial, pero el hecho de que tu comentario original no fuera realmente correcto jugó un papel en el por qué decidí preguntar. :)
Mitch Schwartz