La plus longue sous-chaîne commune en temps linéaire

45

Ce défi consiste à écrire du code pour résoudre le problème suivant.

Étant donné deux chaînes A et B, votre code doit générer les index de début et de fin d'une sous-chaîne de A avec les propriétés suivantes.

  • La sous-chaîne de A doit également correspondre à une sous-chaîne de B.
  • Il ne devrait plus y avoir de sous-chaîne de A qui réponde à la première propriété.

Par exemple:

A = xxxappleyyyyyyy

B = zapplezzz

La sous-chaîne appleavec des index 4 8(indexant à partir de 1) serait une sortie valide.

La fonctionnalité

Vous pouvez supposer que la saisie sera standard dans ou dans un fichier du répertoire local, à vous de choisir. Le format de fichier sera simplement deux chaînes, séparées par une nouvelle ligne. La réponse devrait être un programme complet et pas seulement une fonction.

Je voudrais éventuellement tester votre code sur deux chaînes extraites des chaînes de http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/ .

But

Ceci est du code-golf avec une torsion. Votre code doit être exécuté dans le O(n)temps, où nest la longueur totale de l'entrée.

Langues et bibliothèques

Vous pouvez utiliser n’importe quel langage disposant d’un compilateur / interprète / etc. Disponible gratuitement. pour Linux. Vous ne devez utiliser que des bibliothèques Open Source standard non conçues pour résoudre cette tâche. En cas de litige, je considérerai cela comme n'importe quelle bibliothèque fournie en standard avec votre langue ou que vous pourrez installer sur une machine Ubuntu par défaut à partir d'un référentiel par défaut.

Informations utiles

Il existe au moins deux façons de résoudre ce problème en temps linéaire. L'une consiste à calculer d'abord l'arbre de suffixe et la seconde à calculer d'abord le tableau de suffixes et le tableau LCP.

Communauté
la source
4
O(n) timeEs-tu sûr que c'est possible?
Savenkov Alexey
17
@ Lembik Désolé, ce sont des algorithmes très complexes et ce n'est pas vraiment amusant de générer plus de 100 lignes de code.
FUZxxl
4
L'article sur le deuxième lien que vous fournissez sous "Informations utiles" indique que "la construction d'un [arbre de suffixe] nécessite un temps O (N ^ 2)"
KSFT
3
@ Lembik Vous devriez simplement poser la question [code le plus rapide], où le programme avec le meilleur cas du pire cas en notation big-oh gagne. Alors vous aurez au moins quelques réponses, et même si quelqu'un peut le résoudre en O (n), ils gagneront.
mbomb007
9
Ce doit être la question avec les réponses les plus supprimées par réponse valide ...
FlipTack

Réponses:

39

Python 2, 646 octets

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

Ceci utilise l'algorithme de biais décrit dans "Construction de groupes de suffixes à travail linéaire simple" de Kärkkäinen et Sanders. L'implémentation C ++ incluse dans ce document semble déjà un peu "gaie", mais il y a encore beaucoup de place pour la rendre plus courte. Par exemple, nous pouvons recurse jusqu’à arriver à un tableau de longueur un, au lieu de court-circuiter comme dans le papier, sans violer l’ O(n)exigence.

Pour la partie LCP, j'ai suivi "Calcul du préfixe le plus long, le plus long et le plus linéaire dans les tableaux de suffixes et ses applications" de Kusai et al.

Le programme est généré 1 0si la plus longue sous-chaîne commune est vide.

Voici un code de développement qui inclut une version antérieure du programme qui suit de plus près l'implémentation de C ++, des approches de comparaison plus lentes et un simple générateur de cas de test:

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
la source
1
Corrigez-moi si je me trompe, mais n'est-ce pas en fait 739 octets? J'ai copié dans mothereff.in/byte-counter et supprimé 2 espaces des lignes 6 à 9, mais je ne suis pas sûr que ce soit correct.
Patrick Roberts
2
@ PatrickRoberts Ce sont des onglets.
Mitch Schwartz
2
Bonne réponse! Vous voudrez peut-être jeter un coup d'œil à GSACA, un nouveau SACA à temps linéaire de 2016. L'implémentation de référence compte 246 lignes de commentaires (170 sans commentaires) et semble très jouable. Vous le trouverez sur github.
Christoph
1
@MitchSchwartz J'essaie actuellement de rester sur noPMO, je ne ressens donc pas beaucoup d'émotions pour le moment (probablement à cause de substances chimiques cérébrales mal équilibrées). Au moment de lire rapidement le code, mon moteur de golf à syntaxe l’avait remarquée, et je ne me souviens pas d’avoir ressenti d’émotions spécifiques. Avez-vous pensé à la même chose ou pourquoi la question? :) Maintenant je suis curieux.
Yytsi
1
@ TuukkaX C'est une réponse intéressante à laquelle je ne m'attendais pas. Eh bien, je ne sais pas si je devrais formuler cela de manière particulière, mais le fait que votre commentaire initial ne soit pas vraiment correct a en partie contribué à la raison pour laquelle j'ai décidé de poser la question. :)
Mitch Schwartz