Skip to main content
Code Golf

Return to Answer

added 855 characters in body
Source Link
MickyT
MickyT
  • 12.2k
  • 2
  • 26
  • 48

Seems I was over complicating the problem with the previous solution. This is about 50% quicker (23 secs on 15k strings) than the previous one and pretty simple.

rm(list=ls(all=TRUE))
a="xxxappleyyyyyyy"
b="zapllezzz"
s=proc.time()
matchLen=1
matchIndex=1
indexA = 1
repeat {    
    i = 0
    repeat {
        srch = substring(a,indexA,indexA+matchLen+i)
        if (agrepl(srch,b,max.distance=list(insertions=0,deletions=0,substitutions=1)))
            i = i + 1
        else {
            if (i > 0) {
                matchLen = matchLen + i - 1
                matchIndex = indexA
            }
            break
        }
    }
    indexA=indexA+1
    if (indexA + matchLen > nchar(a)) break
}
c(matchIndex, matchLen + matchIndex)
print (substring(a,matchIndex, matchLen + matchIndex))
print(proc.time()-s)

This will never be a contender due to the language, but I did have a bit of fun doing it.
Not sure of the complexity of it, but over a couple of ~15k strings it takes 43 secs using a single thread. The largest portion of that was the sorting of the arrays. I tried some other libraries, but without significant improvement.

This will never be a contender due to the language, but I did have a bit of fun doing it.
Not sure of the complexity of it, but over a couple of ~15k strings it takes 43 secs using a single thread. The largest portion of that was the sorting of the arrays. I tried some other libraries, but without significant improvement.

Seems I was over complicating the problem with the previous solution. This is about 50% quicker (23 secs on 15k strings) than the previous one and pretty simple.

rm(list=ls(all=TRUE))
a="xxxappleyyyyyyy"
b="zapllezzz"
s=proc.time()
matchLen=1
matchIndex=1
indexA = 1
repeat {    
    i = 0
    repeat {
        srch = substring(a,indexA,indexA+matchLen+i)
        if (agrepl(srch,b,max.distance=list(insertions=0,deletions=0,substitutions=1)))
            i = i + 1
        else {
            if (i > 0) {
                matchLen = matchLen + i - 1
                matchIndex = indexA
            }
            break
        }
    }
    indexA=indexA+1
    if (indexA + matchLen > nchar(a)) break
}
c(matchIndex, matchLen + matchIndex)
print (substring(a,matchIndex, matchLen + matchIndex))
print(proc.time()-s)

This will never be a contender due to the language, but I did have a bit of fun doing it.
Not sure of the complexity of it, but over a couple of ~15k strings it takes 43 secs using a single thread. The largest portion of that was the sorting of the arrays. I tried some other libraries, but without significant improvement.

Source Link
MickyT
MickyT
  • 12.2k
  • 2
  • 26
  • 48

R

This will never be a contender due to the language, but I did have a bit of fun doing it.
Not sure of the complexity of it, but over a couple of ~15k strings it takes 43 secs using a single thread. The largest portion of that was the sorting of the arrays. I tried some other libraries, but without significant improvement.

a="xxxappleyyyyyyy"
b="zapllezzz"
s=proc.time()
N=nchar
S=substring
U=unlist
V=strsplit
A=N(a)
B=N(b)
a=S(a,1:A)
b=S(b,1:B)
a=sort(a,method="quick")
b=sort(b,method="quick")
print(proc.time()-s)
C=D=1
E=X=Y=I=0
repeat{
    if(N(a[C])>E && N(b[D])>E){
        for(i in E:min(N(a[C]),N(b[D]))){
            if (sum(U(V(S(a[C],1,i),''))==U(V(S(b[D],1,i),'')))>i-2){
                F=i
            } else break
        }
        if (F>E) {
            X=A-N(a[C])+1
            Y=X+F-1
            E=F
        }
        if (a[C]<b[D])
            C=C+1
            else
            D=D+1
    } else
        if(S(a[C],1,1)<S(b[D],1,1))C=C+1 else D=D+1
    if(C>A||D>B)break
}
c(X,Y)
print(proc.time()-s)

Method:

  • Create a suffix array for each string
  • Order the suffix arrays
  • Step through each of the arrays in a staggered sort of way comparing the beginning of each