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