Algorithms: Longest substring in linear time.

It is unlikely that there is a better algorithm than the quadratic one, and much less linear. For the related problem of finding subsequences, this is a known result: in the document "Narrow hardness results for LCS and other measures of sequence similarity". by Abboud et al. , show that the existence of an algorithm with a time of execution of $ O (n ^ {2- varepsilon}) $, for some $ varepsilon> 0 $ refutes the Strong Exponential Time Hypothesis (SETH).

It is considered that SETH is very probable (although not universally accepted), so it is unlikely that $ O (n ^ {2- varepsilon}) $ the time algorithm exists.


While the search for a substring is a slightly different problem, it seems likely to be equally difficult.