When aligning two products there might be a further chance of optimization.
The observation is that if at a certain step we perform a match (%) followed by an insertion (+) then the alignment problem we are left with, is the same that we would have if we performed an insertion followed by a match.
This is not completely true with the current optimization, when we are in the %+ case, if we can generate %%, then we are not going to generate %+-. However, in the case of +%, we have to account for +%- aswell.
My idea is that whenever we perform a %, then we could build some sort of memoization table that will be passed along to the + and - cases allowing us to avoid recomputing at least half of the alignments.
When aligning two products there might be a further chance of optimization.
The observation is that if at a certain step we perform a match (%) followed by an insertion (+) then the alignment problem we are left with, is the same that we would have if we performed an insertion followed by a match.
This is not completely true with the current optimization, when we are in the %+ case, if we can generate %%, then we are not going to generate %+-. However, in the case of +%, we have to account for +%- aswell.
My idea is that whenever we perform a %, then we could build some sort of memoization table that will be passed along to the + and - cases allowing us to avoid recomputing at least half of the alignments.