Day-16: Smith - Waterman Algorithm

Smith - Waterman algorithm is the version of Needleman - Wunsch that computes the best local alignment.

The solution changes with just one more predicate added to recurrence relation of dynamic table.

The algorithm simply gives free rides to the starting point that allows it to never get under 0.

Time complexity: O(nm) where n is the length of the first string and m is the length of the second one.

Here is the link of my C++ implementation of Smith- Waterman: Smith- Waterman