Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!ub!ajay
From: ajay@cs.Buffalo.EDU (Ajay Shekhawat)
Newsgroups: comp.theory
Subject: Longest repeated substring problem.
Message-ID: <70943@eerie.acsu.Buffalo.EDU>
Date: 15 Apr 91 18:08:55 GMT
Sender: news@acsu.Buffalo.EDU
Reply-To: ajay@cs.Buffalo.EDU ( Ajay Shekhawat )
Organization: University at Buffalo, Dept. of Computer Science
Lines: 13
Nntp-Posting-Host: sybil.cs.buffalo.edu
Originator: ajay@sybil.cs.Buffalo.EDU


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..


Ajay Shekhawat           <Dept. of Comp. Sci., SUNY@Buffalo, Amherst, NY 14260>
ajay@cs.Buffalo.EDU || ajay@sunybcs.BITNET || ajay@sunybcs.UUCP || 716.636.3180