3.1. Longest Common Subword Problem

Try these first

1. 1.

   Define what a common subword is in your own words.

   Hint

   Think about parts of words you see in other words.

2. 2.

   What does the brute force method do?

   Hint

   Consider how we could manually find matches.

3. 3.

   What is a common subword?

   Hint

   Think of segments of strings.

4. 4.

   True or False: The brute force method has a time complexity of O(m * n).

   Hint

   Consider the multiple comparisons involved.

5. 5.

   Given the words 'intention' and 'attention', find their longest common subword using dynamic programming.

   Hint

   Display a matrix to find each character match.

6. 6.

   Write an efficient algorithm in pseudo-code that uses dynamic programming to find the length of the longest common subword between two given strings.

   Hint

   Ensure to handle base cases properly when initializing the table.