Longest common substring in linear time
Python 2, 646 bytes

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):
&#9;b=[[]for _ in s];c=[]
&#9;for x in B[:N]:b[s[x+o]]+=x,
&#9;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)&gt;r(0);N-=n/3
 for x in B*1:v=s[x:x+3];m+=u&lt;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&lt;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&lt;N&lt;(s[i:i-~b],J[i/3+b+N-b*N])&gt;(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&gt;0;j=S[I[i]-1]
 while s[i+h]==s[j+h]:h+=1
 if(i&lt;t)==(t&lt;j)&lt;=h&gt;m:m=h;L=min(i,j)
print-~L,L+m

Try it online
This uses the skew algorithm described in &quot;Simple Linear Work Suffix Array Construction&quot; by Kärkkäinen and Sanders. The C++ implementation included in that paper already feels a little &quot;golfy&quot;, but there is still plenty of room for making it shorter. For example, we can recurse until arriving at an array of length one, instead of short circuiting as in the paper, without violating the O(n) requirement.
For the LCP part, I followed &quot;Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications&quot; by Kasai et al.
The program outputs 1 0 if the longest common substring is empty.
Here is some development code that includes an earlier version of the program that follows the C++ implementation a bit more closely, some slower approaches for comparison, and a simple test case generator:
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&gt;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&lt;1 or R&gt;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&gt;m and len(a)==sorted([i,j,len(a)])[1]:
                m=h
                L=min(i,j)
                R=L+h
            h-=h&gt;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&lt;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&lt;n0]
    radix_pass(B,0,n0)
    
    R=[]
    
    p=0
    t=adj
    while t&lt;n02:
        x=A[t]
        b=x&gt;=n0
        i=(x-b*n0)*3-~b
        j=B[p]
        if p==n0 or ((s[i:i+2],I[A[t]-n0+1])&lt;(s[j:j+2],I[j/3+n0]) if b else (s[i],I[A[t]+n0])&lt;(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&gt;m and len(a)==sorted([i,j,len(a)])[1]:
                m=h
                L=min(i,j)
                R=L+h
            h-=h&gt;0
    
    return L+1,R

stress_test(solve)