The time complexity of the dynamic programming approach for the longest common substring problem is _______.

  • O(n log n)
  • O(n)
  • O(n^2)
  • O(nm)
The time complexity of the dynamic programming approach for the longest common substring problem is O(nm), where 'n' and 'm' are the lengths of the input strings. The algorithm uses a table of size n x m to store intermediate results, leading to a quadratic time complexity.
Add your answer
Loading...

Leave a comment

Your email address will not be published. Required fields are marked *