A slight modification of the Needleman Wunsch algorithm yields a local sequence similarity algorithm (Michael Waterman is quoted as saying that this was more publicity than he dared to think he'd get just for adding a zero to published work). The Smith Waterman algorithm uses the same objective function as the Needleman Wunsch algorithm (so you should read that node!), but searches for the two substrings with the highest similarity score.
Since Needleman Wunsch runs in time O(m n), when the sequences have lengths m and n, it would appear that you'd need time O(m3 n3) to do this. However, a minor modification of the dynamic programming algorithm used there yields local sequence similarity in time O(m n). In the dynamic programming matrix for Needleman Wunsch, element (i,j) contains the highest score for a partial alignment of letters 1, ..., i of the first sequence to letters 1, ..., j of the second. To be able to do the same thing for a local sequence similarity measure, one more rule is added to the update rule for the Needleman Wunsch algorithm: Any (match) cell with a negative score is changed to score 0. This represents the fact the a local alignment could always start at that cell, scoring (so far) 0, and would be better than any negative score. Similarly, when the matrix is complete, the alignment score is taken to be the maximum over the entire matrix (whereas Needleman Wunsch just takes the score at the far corner of the matrix).
Bellman probably knew all of this, too.