================================
Implementation of Hirschberg's algorithm; linear space implementation of dynamic programming
The factor that limits dynamic programing's application often is not its running time (O(nm)) but the quardratic space requirement, where n and m are the length of two sequence. The Hirschberg algorithm reduces the space requirement from O(nm) to O(n) by involves divide and conque technique in the dynamic Programming process. Below is an implementation of Hirschberg's algorithm.