Algorithm Implementation/Strings/Longest common substring - Wikibooks, open books for an open world

Common dynamic programming implementations for the Longest Common Substring algorithm runs in O(nm) time. All of these implementations also use O(nm) storage. The astute reader will notice that only the previous column of the grid storing the dynamic state is ever actually used in computing the next column. Thus, these algorithm can be altered to have only an O(n) storage requirement. By reassigni