[R](http://www.r-project.org/)
=

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