4..7. LCS Code Implementation

So, we have seen earlier that if we just look blindly at every position and try to scan the word starting that position, we get something which is an order m, n square. now, this solution when require as to fill in the table of size m time n, so obviously, every entry in the m times n table, we just have to look at a neighbors to fill it up. So, it is a constant time operation.

The process of finding the longest common subsequence (LCS) involves checking each position in one word against another. If you naively scan from each position, this results in an inefficient O(m*n) process, where m and n are the lengths of the two strings. A better approach uses a table of size m x n to store intermediate results and significantly reduces the computation time by only looking at 'neighbor' entries.

Consider trying to match words in two dictionaries. If you just flip through each dictionary one page at a time, it would take a long time. However, if you note the words you've already examined and use them to help match the remaining ones, you'll find matches much more efficiently.

So, we can now look at a slightly more general problem than longest common subword in one which is more interesting computationally. So, what if we do not look for an exact match, but we allow a self should drop some letters. So, we have a subsequence not a sub word, it allows us to drop some letters and now, if you want to know, after dropping some letters, what is the longest match we can find.

The LCS problem is not about matching entire sequences directly, but rather about finding the longest series of characters that appear in both sequences while allowing for some characters to be ignored. This is known as allowing a subsequence, which leads to potentially longer matching sequences when characters can be dropped.

Imagine trying to find a matching necklace among different styles. If you allow for missing beads or colors (i.e., you can drop some parts), you may find a longer matching sequence than if you insist that every bead must be present to count.

So, before we proceed it useful to look at why the longest common subsequence problem is interesting. One of the area is an bio informatics. So, biologist are interested in identifying, how close two species are each other in the genetic sense. So, if we look at are DNA, our DNA is basically a long string over an alphabet of size 4.

The LCS algorithm has practical use cases, notably in bioinformatics, where it helps determine genetic similarities between species by comparing DNA sequences. The DNA can be treated as strings of letters, and the LCS helps show how closely related two organisms are by highlighting similar sequences.

Think of DNA as a recipe book. When comparing two versions of a recipe, you want to find the common ingredients that exist between them. The LCS is similar to finding those shared ingredients in the two recipes, showing how two different meals can be similar at their core.

So, as usual let LCS i comma j, stand for the LCS of the problem starting at a i and b j. So, if a i equal b j as we say, LCS of i j is 1 plus LCS of i plus 1 j plus 1.

The approach to solve LCS is inductive. If two characters from the sequences match, you include them in your count (hence adding 1). Then you reduce the problem to finding the LCS for the remaining characters. In cases where the characters do not match, you explore two new subproblems by either advancing the first or the second sequence, ensuring you do not overlook any potential matches.

Consider climbing a mountain: if you reach a resting point that matches the level of another mountain, you count this as a step taken together. If they don't match, you either need to step up the second mountain or step back on the first one, allowing you to find the highest reach of both mountains (LCS).

So, this is similar to LCW, we basically fill out in m, n size table each entry in the table is easy to compute takes only constant among look at the three neighbors. And therefore, overall using dynamic programming, we have demonstrated an order m n algorithm.

The implementation of the LCS algorithm involves creating a dynamic programming table of size m x n. Each cell in this table is computed using previously calculated values (neighbors in comparison), and the final result emerges from accumulated values within this organized structure. This design ensures efficiency, leading to a manageable time complexity unlike naive approaches.

Think of filling out a large schedule or planner. You can easily see what appointments are lined up next to each other. By using previously filled slots (i.e., neighbors), you effectively plan your schedule without redoing the work for every meeting, making it much more efficient.

--