3.2. Brute Force Algorithm

Try these first

1. 1.

   What is a common subword?

   Hint

   Think about what part of the words is the same.

2. 2.

   How does a brute force algorithm work?

   Hint

   Consider a systematic approach to find matches.

3. 3.

   What is the aim of the brute force algorithm in this context?

   • To find the longest common subword
   • To sort the strings
   • To compare character frequencies

   Hint

   Remember the problem we are trying to solve.

4. 4.

   Brute force algorithms have a complexity of O(m * n^2).

   • True
   • False

   Hint

   Reflect on how many iterations are required.

5. 5.

   Implement a brute force solution in Python to find the longest common subword.

   Hint

   Consider breaking your code into smaller functions for matching segments.

6. 6.

   Devise a dynamic programming approach to optimize the search for the longest common subword.

   Hint

   Think about how you can store and reuse lengths of already found subwords.