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!mimsy!mimsy.umd.edu!mpf
From: mpf@triplea.cs.umd.edu (Martin Farach)
Newsgroups: comp.theory
Subject: Re: Longest repeated substring problem.
Message-ID: <MPF.91Apr15210650@triplea.cs.umd.edu>
Date: 16 Apr 91 01:06:50 GMT
References: <70943@eerie.acsu.Buffalo.EDU>
	<1991Apr15.200508.757@bingvaxu.cc.binghamton.edu>
Sender: news@mimsy.umd.edu
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 25

In article <1991Apr15.200508.757@bingvaxu.cc.binghamton.edu> kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell) 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.
   >
   >Ajay..

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

   -kym

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

--
Martin Farach			mpf@cs.umd.edu
University of Maryland		"Triviality and certainty are the
Department of Computer Science	 kinderkrankheiten of knowledge."
College Park, Maryland 20742			  -Imre Lakatos