search

jainaman224 / Algo_Ds_Notes

A comprehensive resource for learning and implementing algorithms and data structures. This repository includes detailed notes, complexity analysis, and code examples in C++, Java, Python, and more. Ideal for students, professionals, and those preparing for coding interviews.
GNU General Public License v3.0
2.24k stars 2.09k forks source link

Longest common Substring in C++, Java and Python. #667

Closed prashant-mahanta closed 5 years ago

prashant-mahanta commented 5 years ago

I want to add the Longest common substring algorithm which is commonly known as LCS in C++, Java, and Python. The Time complexity of the algorithm O(n*m) and Space complexity O(n) using DP Link: Longest Common Substring_Wikipedia Can I go ahead with this?

jainaman224 commented 5 years ago

It is already assigned. https://github.com/jainaman224/Algo_Ds_Notes/issues/610

prashant-mahanta commented 5 years ago

@jainaman224 my approach is for strings and with a space complexity of O(n). The PR which is merged for longest common subsequence is for integer array with a space complexity of O(m*n).

jainaman224 commented 5 years ago

@prashant-mahanta Is there any specific name to the algorithm?

prashant-mahanta commented 5 years ago

@jainaman224 No, the Longest Common Substring is usually the problem called. It's the implementation difference, instead of a mn matrix we can keep a 2n matrix to reduce the space complexity(as we only need the adjacent rows only) from O(m*n) to O(n).