3.1. Longest Common Subword Problem

Let us now turn to the problem of finding Common Subwords and Subsequences between two sequences. The longest common subword problem involves finding the length of the longest common subword between two strings. A subword is simply a segment of a word. For example, if we have the words 'secret' and 'secretary', the longest common subword is 'secret', which has a length of 6.

In this section, we are introduced to the longest common subword problem, which focuses on finding the maximum length of segments that two different words may share. The term 'subword' refers to a continuous sequence of characters in a word, similar to how the phrase 'looking for a needle in a haystack' metaphorically relates to finding something specific within a big mass of data.

Think of trying to find the longest common sequence of characters in two different pieces of text, like looking for common phrases that appear in both documents. For instance, if the two documents were recipes, the ingredient 'egg' could be a common subword of a length of 3.

We have two words a[0] to a[m] and b[0] to b[n]. We say that if we can find segments starting with a[i] and b[j], reading k letters from each, that are equal, then these segments have a common subword of length k.

Formally, we define two sequences of characters, with ‘a’ covering one word and ‘b’ covering another. The characters can be indexed, and if we can match a substring from ‘a’ starting at index ‘i’ with a substring from ‘b’ starting at index ‘j’ for a length ‘k’, we have identified a common subword. The challenge thus lies in calculating the length of the longest segment that can match this criterion.

Similar to finding the longest common route two friends might take to reach the same destination from different starting points, where the common route represents the matching characters in two words.

A brute force algorithm would try every position in both strings. For every pair of characters starting at a[i] from the first word and b[j] from the second word, we check if they match. If they do, we continue matching, looking next at a[i+1] and b[j+1] until a mismatch occurs.

The brute force method involves systematically checking every possible starting point in both words for potential matches. Essentially, for every character in ‘a’, the algorithm starts checking from that character and continues matching characters in ‘b’ where possible. This simple method, however, becomes computationally slow as the size of the input increases, leading to an O(m*n) complexity.

Imagine trying different combinations of two sets of book titles to find the longest overlap. You'd start comparing from the first title of each set, checking each title in sequence—just like finding the longest shared phrase between two essays.

The first inductive observation shows that if there’s a common subword of length k at a[i], b[j], there must also be a common subword of length k-1 at a[i+1], b[j+1]. If a[i] does not equal b[j], we cannot extend any common subword.

This chunk shifts to an inductive reasoning framework, which allows us to conclude that if two characters match, the next characters must also form a common segment that is one character shorter. If they do not match, then no common extension can occur for that particular matching attempt. This observation creates a simple relationship between consecutive lengths.

Think of building a Lego structure: if you found two connecting pieces, you can keep stacking more pieces on top as long as they fit. Conversely, if you find that a piece doesn't fit, the stack can't grow from that connection.

We can implement a dynamic programming solution to store computed subproblems, where LCW[i][j] represents the length of the longest common subword of strings ending at positions i and j. The computation involves checking dependencies between the current characters and previously computed lengths.

Dynamic programming improves efficiency by storing computed solutions to smaller segments of the problem, thereby avoiding repeated calculations. We create a table where each entry corresponds to the length of the longest common subword for segments of two words. This way, we can build up the solution iteratively from these smaller problems.

Consider a student creating a study guide. Instead of rewriting all information for each new topic, they maintain a reference of what they've already summarized, so they can simply expand or adjust previous summaries, thus saving time and effort.

Ultimately, after populating the dynamic programming table, finding the maximum value within it yields the length of the longest common subword. The corresponding segments can also be traced back using the table.

After building the dynamic programming table, you search for the largest value present. This value corresponds to the longest common segment found between the two input words. Additionally, through backtracking in the table, one can identify the actual characters that make up that common subword, though our primary goal is simply to return its length.

This is similar to searching for the tallest building in a city skyline and then figuring out which buildings contributed to its height by looking at their foundations.

--