Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!rpi!sarah!bingnews!kym
From: kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell)
Newsgroups: comp.theory
Subject: Re: Longest repeated substring problem.
Message-ID: <1991Apr15.200508.757@bingvaxu.cc.binghamton.edu>
Date: 15 Apr 91 20:05:08 GMT
References: <70943@eerie.acsu.Buffalo.EDU>
Organization: State University of New York at Binghamton
Lines: 14

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