Content deleted Content added
No edit summary |
|||
Line 19:
==Algorithms==
One can find the lengths and starting positions of the longest common substrings of <math>S</math> and <math>T</math> in [[Big O notation#Family of Bachmann–Landau notations|<math>\Theta</math>]]<math>(n+m)</math> time with the help of a [[generalized suffix tree]]. A faster algorithm can be achieved in the [[word RAM]] model of computation if the size <math>\sigma</math> of the input alphabet is in <math>2^{o(\sqrt{\log(n+m)})}</math>. In particular, this algorithm runs in <math>O((n+m)\log\sigma/\sqrt{\log (n+m)})</math> time using <math>O((n+m)\log\sigma/\log (n+m))</math> space.<ref name="CKPR21">{{cite conference | last1 = Charalampopoulos | first1 = Panagiotis | last2 = Kociumaka | first2 = Tomasz | last3 = Pissis | first3 = Solon P. | last4 = Radoszewski | first4 = Jakub | year = 2021 | title = Faster Algorithms for Longest Common Substring | conference = European Symposium on Algorithms | doi = 10.4230/LIPIcs.ESA.2021.30}}</ref> Solving the problem by [[dynamic programming]] costs <math>\Theta(nm)</math>. The solutions to the generalized problem take <math>\Theta(n_1 + ... + n_K)</math> space and <math>\Theta(n_1</math>·...·<math>n_K)</math> time with [[dynamic programming]] and take <math>\Theta(N * K)</math> time with [[generalized suffix tree]].
===Suffix tree===
| |||