Substring umum terpanjang dalam waktu linier

45

Tantangan ini adalah tentang menulis kode untuk menyelesaikan masalah berikut.

Diberikan dua string A dan B, kode Anda harus menampilkan awal dan akhir indeks substring A dengan properti berikut.

  • Substring A juga harus cocok dengan beberapa substring B.
  • Seharusnya tidak ada lagi substring A yang memenuhi properti pertama.

Sebagai contoh:

A = xxxappleyyyyyyy

B = zapplezzz

Substring appledengan indeks 4 8(pengindeksan dari 1) akan menjadi output yang valid.

Fungsionalitas

Anda dapat berasumsi bahwa input akan sesuai standar atau dalam file di direktori lokal, itu adalah pilihan Anda. Format file hanya akan menjadi dua string, dipisahkan oleh baris baru. Jawabannya harus berupa program lengkap dan bukan hanya fungsi.

Saya akhirnya ingin menguji kode Anda pada dua substring yang diambil dari string di http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/ .

Skor

Ini adalah kode-golf dengan twist. Kode Anda harus dijalankan dalam O(n)waktu, di mana ntotal panjang input.

Bahasa dan perpustakaan

Anda dapat menggunakan bahasa apa pun yang memiliki kompiler / interpreter / dll yang tersedia secara bebas. untuk Linux. Anda hanya harus menggunakan pustaka sumber terbuka standar yang tidak dirancang untuk menyelesaikan tugas ini. Jika terjadi perselisihan, saya akan menghitung ini sebagai pustaka mana pun yang datang sebagai standar dengan bahasa Anda atau yang dapat Anda instal di mesin ubuntu default dari repositori default.

Informasi berguna

Setidaknya ada dua cara untuk menyelesaikan masalah ini dalam waktu linier. Pertama adalah menghitung pohon sufiks pertama dan yang kedua adalah pertama menghitung array sufiks dan array LCP.

Komunitas
sumber
4
O(n) timeApakah Anda yakin itu mungkin?
Savenkov Alexey
17
@ Lembik Maaf, tetapi ini adalah algoritma yang sangat kompleks dan tidak terlalu menyenangkan untuk mengelompokkan 100+ baris kode.
FUZxxl
4
Artikel di tautan kedua yang Anda berikan di bawah "Informasi bermanfaat" mengatakan bahwa "membangun [pohon sufiks] membutuhkan waktu O (N ^ 2)"
KSFT
3
@Lembik Anda hanya harus membuat pertanyaan [kode tercepat], di mana program dengan kasus terburuk terbaik dalam notasi oh besar menang. Maka Anda setidaknya akan mendapatkan beberapa jawaban, dan bahkan pada saat seseorang dapat menyelesaikannya dalam O (n), mereka akan menang.
mbomb007
9
Ini pasti pertanyaan dengan jawaban paling banyak dihapus per jawaban yang valid ...
FlipTack

Jawaban:

39

Python 2, 646 byte

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

Ini menggunakan algoritma miring yang dijelaskan dalam "Konstruksi Susunan Sufiks Kerja Linier Sederhana" oleh Kärkkäinen dan Sanders. Implementasi C ++ termasuk dalam makalah itu sudah terasa sedikit "golfy", tetapi masih ada banyak ruang untuk membuatnya lebih pendek. Sebagai contoh, kita bisa berulang sampai tiba pada array yang panjangnya satu, bukannya hubungan arus pendek seperti di kertas, tanpa melanggar O(n)persyaratan.

Untuk bagian LCP, saya mengikuti "Komputasi Linear-Waktu Terpanjang-Umum-Awalan dalam Susunan Sufiks dan Aplikasinya" oleh Kusai et al.

Program mengeluarkan 1 0jika substring umum terpanjang kosong.

Berikut adalah beberapa kode pengembangan yang mencakup versi program yang lebih awal yang mengikuti implementasi C ++ sedikit lebih dekat, beberapa pendekatan yang lebih lambat untuk perbandingan, dan generator case uji sederhana:

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
sumber
1
Perbaiki saya jika saya salah, tetapi bukankah ini sebenarnya 739 byte? Saya menyalin ke mothereff.in/byte-counter dan menghapus 2 spasi dari baris 6-9, tapi saya tidak yakin apakah itu benar.
Patrick Roberts
2
@ PatrickRoberts Itu adalah tab.
Mitch Schwartz
2
Jawaban bagus! Anda mungkin ingin melihat GSACA waktu linier baru SACA dari 2016. Implementasi referensi adalah 246 baris penuh komentar (170 tanpa komentar) dan tampaknya sangat golf. Anda akan menemukannya di github.
Christoph
1
@MitchSchwartz Saat ini saya mencoba untuk tetap pada noPMO, jadi saya tidak bisa merasakan emosi dengan kuat sekarang (mungkin karena bahan kimia otak yang tidak seimbang). Pada saat membaca kode dengan cepat, motor golf sintaksis saya melihatnya, dan saya tidak ingat merasakan emosi tertentu. Apakah Anda memikirkan hal yang sama atau mengapa pertanyaan itu? :) Sekarang saya penasaran.
Yytsi
1
@ TuukkaX Itu respon menarik yang tidak saya duga. Yah, saya tidak yakin apakah saya harus mengutarakan ini dengan cara khusus, tetapi fakta bahwa komentar asli Anda sebenarnya tidak benar berperan dalam mengapa saya memutuskan untuk bertanya. :)
Mitch Schwartz