Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!sample.eng.ohio-state.edu!purdue!haven!ni.umd.edu!uc780.umd.edu!cs450a03
From: cs450a03@uc780.umd.edu
Newsgroups: comp.theory
Subject: RE: Longest repeated substring problem.
Message-ID: <15APR91.23045679@uc780.umd.edu>
Date: 15 Apr 91 23:04:56 GMT
References: <70943@eerie.acsu.Buffalo.EDU> <MPF.91Apr15210650@triplea.cs.umd.edu>
Sender: usenet@ni.umd.edu (USENET News System)
Organization: The University of Maryland University College
Lines: 19

Martin Farach  >
Kym Horsell    >|
Ajay Shekhawat >***

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

>| If you mean _consecutive_ repetitions it can be done in linear time.

>Actually, it can done in linear time whether or not it is consecutive
>repetitions.  Just build a suffix tree.

I don't think that you can guarantee that building the suffix tree
will take linear time.  (Consider using a fun string, like
'abbabaabbaaba...')

Raul Rockwell