Content deleted Content added
m Updated memory saving tricks for the Dynamic Programming method. |
m Fixed definition of array L in the DP solution. |
||
Line 53:
'''return''' ret
This algorithm runs in <math>O(n r)</math> time. The array <code>L</code> stores the length of the longest common substring of the prefixes <code>S[1..i]</code> and <code>T[1..j]</code> which ''end at position'' <code>S[i]</code>, <code>T[j]</code>, resp. The variable <code>z</code> is used to hold the length of the longest common substring found so far. The set <code>ret</code> is used to hold the set of strings which are of length <code>z</code>. The set <code>ret</code> can be saved efficiently by just storing the index <code>i</code>, which is the last character of the longest common substring (of size z) instead of <code>S[i-z+1..i]</code>. Thus all the longest common substrings would be, for each i in <code>ret</code>, <code>S[(ret[i]-z)..(ret[i])]</code>.
The following tricks can be used to reduce the memory usage of an implementation:
| |||