Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!crdgw1!uunet!mcsun!corton!chorus!nocturne.chorus.fr!jloup
From: jloup@nocturne.chorus.fr (Jean-Loup Gailly)
Newsgroups: comp.theory
Subject: Re: Longest repeated substring problem.
Message-ID: <9349@chorus.fr>
Date: 16 Apr 91 09:16:08 GMT
References: <70943@eerie.acsu.Buffalo.EDU>
Sender: jloup@chorus.fr
Reply-To: jloup@nocturne.chorus.fr (Jean-Loup Gailly)
Organization: Chorus systemes, Saint Quentin en Yvelines, France
Lines: 19

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 ) ?

This problem can be solved in linear time [O(n)] using a suffix tree.
See for example

     McCreight,E.M.
     A space-economical suffix tree construction algorithm
     JACM 23, 2 (1976), 262-272

Jean-loup Gailly

Chorus systemes, 6 av G. Eiffel, 78182 St-Quentin-en-Yvelines-Cedex, France
email: jloup@chorus.fr    Tel: +33 (1) 30 64 82 79 Fax: +33 (1) 30 57 00 66