3.4. Dynamic Programming Approach

Let us now turn to the problem of finding Common Subwords and Subsequences between two sequences. The first problem we look at is what is called a longest common subword problem. We are given two words and want to find the length of the longest common subword between them. A subword is just a segment, for instance, with the words 'secret' and 'secretary', the longest common subword is 'secret' with length 6.

In this chunk, we are introduced to the longest common subword problem, which involves finding a segment that appears in two different words. The term 'subword' refers to a continuous part or segment of a string. Examples include finding 'isect' in 'bisect' and 'trisect' or 'sec' in 'bisect' and 'secret'. The main aim here is not just to find the common subword itself but to determine its length.

Think of it like searching for common phrases in two different books. For example, if one book says 'The quick brown fox' and another book says 'A quick brown dog', the common phrase 'quick brown' appears in both. Here, the focus is on identifying that commonality.

We have two words a_0 to a_m and b_0 to b_n. We want to check segments starting with positions a_i and b_j, and see if reading k letters from both results in the same segments. The aim is to find the length of the longest such segment.

This chunk formalizes the problem by defining the structure of the two words. Each word consists of characters indexed from 0 to its respective length. By checking every possible starting position in both words, we can compare segments of length k to identify if they match. The focus remains on determining the maximum length of these matching segments.

Imagine two strings of beads – one is red and the other blue. You want to find a sequence of beads that matches between the two strings. You would take different starting points and compare until you find the longest sequence that looks alike.

A brute force algorithm could involve trying every position a_i and b_j and matching letters until a mismatch is found. This could take O(m * n^2) due to the number of comparisons made.

This chunk discusses a basic method to solve the problem: the brute-force algorithm. It suggests checking each character in the first word against every character in the second word, continuing to compare until a mismatch occurs. This method is inefficient because the potential combinations of starting positions lead to a large number of comparisons, specifically O(m * n^2), where m and n are the lengths of the two words.

Imagine trying to find the longest matching sequence of puzzle pieces between two sets by examining each piece one by one. It would take a long time to check each piece of each set until you find the longest matching sequence.

If we have a_i == b_j, then we check the next positions i+1 and j+1, since there's a common subword of one character. Otherwise, we declare the common subword length as 0.

Here, we learn about the inductive nature of the problem. If two characters match, we can extend our search for a common subword to the next positions. If they do not match, then we cannot extend a common subword from that point, and it resets to zero. This insight allows us to approach the problem more efficiently than brute force by building on known results incrementally.

It’s like a game where you only score points when two players starting from the same position make matching moves. If they falter or one moves differently, they lose their score from that round, and the tally resets. But if they match, they can keep going and build their score higher.

A dynamic programming solution is established through subproblems, LCW(i, j), which relies on checking if a_i equals b_j.

In this chunk, we discuss moving from the idea of brute force to dynamic programming. The longest common subword (LCW) is identified as a subproblem where the solution depends on previously computed values. The algorithm builds up from smaller problems, utilizing the results of previous computations to efficiently solve larger problems.

Think of this like assembling a jigsaw puzzle. Instead of starting from scratch with each piece, you remember which pieces fit together as you work on the final picture, thus making the overall process faster and more organized.

After filling the table, we need to determine the entry with the largest value representing the length of the longest common subword.

Once we compute the values in the dynamic programming table, we look for the largest entry, which indicates the length of the longest common subword. This process is performed systematically by analyzing each computed value until we identify the maximum.

Imagine you are collecting points while playing a video game. At the end of the game, you check your score against your friends to see who scored the highest. The maximum score indicates the best performance, just like we identify the longest common subword by finding the maximum value in the table.

To find the longest common subword itself, it can be easily retrieved using the maximum length entry and following the paths in the dynamic programming table.

This chunk explains how we can retrieve the actual longest common subword once the length is identified. By backtracking through the table, we can trace back the matching characters to reconstruct the subword.

It’s like retracing your steps back to a location from a map – once you reach your destination (the maximum length), you can follow the routes you’ve taken (the paths in the table) to return or find out what you passed by.

The dynamic programming version is presented with code detailing how to evaluate the table column by column.

In the final chunk, the implementation details are discussed, explaining how the algorithm is structured in code. It elaborates on filling the dynamic programming table and updating maximum values as comparisons are made. Understanding this implementation is crucial for applying the theoretical knowledge into practical coding.

Think of writing down a recipe. Each step incorporates previous steps and at the end of the recipe, you arrive at the final dish. Similarly, coding this algorithm step by step builds up the solution methodology, leading to the final answer effectively.

--