Newsgroups: comp.theory
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!sarah!bingnews!kym
From: kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell)
Subject: Re: Longest repeated substring problem.
Message-ID: <1991Apr16.154935.21123@bingvaxu.cc.binghamton.edu>
Organization: State University of New York at Binghamton
References: <70943@eerie.acsu.Buffalo.EDU> <1991Apr15.200508.757@bingvaxu.cc.binghamton.edu> <MPF.91Apr15210650@triplea.cs.umd.edu>
Date: Tue, 16 Apr 1991 15:49:35 GMT

In article <MPF.91Apr15210650@triplea.cs.umd.edu> mpf@triplea.cs.umd.edu (Martin Farach) writes:
>   In article <70943@eerie.acsu.Buffalo.EDU> ajay@cs.Buffalo.EDU ( Ajay Shekhawat ) writes:
>   >
>   >Sometime ago I stumbled across this problem: 
>   >Given a string, find the longest repeated substring of
>   >that string. Can this problem be solved in time better
>   >than O(n^2) ( where  n = length of the string ) ?
>   >
>   >Any references would be appreciated.
>Actually, it can done in linear time whether or not it is consecutive
>repetitions.  Just build a suffix tree.

Please elucidate.

-kym