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

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.

• Voici une explication complète et (peut-être trop) détaillée de la construction de l’arbre de suffixes temporels linéaires (il s’avère que certaines des figures sont malheureusement altérées). Il existe également une très bonne réponse SO concernant la construction de l’arborescence de suffixes temporels linéaires à l’ adresse https://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english . Il comprend également un lien vers le code source. Une autre explication détaillée peut être trouvée ici , donnant cette fois une solution complète en C.
• La section 2 de http://www.cs.cmu.edu/~guyb/realworld/papersS04/KaSa03.pdf donne un algorithme de construction de tableau de suffixes temporels linéaires et l'annexe A contient un code source C ++. Cette réponse vous indique comment alors calculer la plus longue sous-chaîne commune https://cs.stackexchange.com/questions/9555/computing-the-longest-common-substring-of-two-strings-using-suffix-arrays . La section 5 de https://courses.csail.mit.edu/6.851/spring12/scribe/lec16.pdf est également associée à une conférence vidéo https://courses.csail.mit.edu/6.851/spring12/lectures/L16. .html explique également le même algorithme à partir de 1:16:00.

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)