Introduction If you are new to string search, I would recommend to first read the brute force approach here. Brute force as discussed in the mentioned post has time complexity of O(mn) in worst case. Rabin-Karp also has the worst case time complexity of O(mn), but it has a much better time complexity of O(mContinue reading “A Simple Explanation of Rabin-Karp Algorithm For String Search”
Tag Archives: Algorithm for interview
Dynamic Programming : An example showing Lowest Common Subsequence in Java
Introduction Optimal Substructure : A problem is said to be a optimal substructure if an optimal solution can be constructed from optimal solution of it’s subproblem. Overlapping subproblems : A problem is said to have overlapping subproblems if the problem can be broken down into repetitive subproblems. Greedy Algorithm is used to solve problems having optimalContinue reading “Dynamic Programming : An example showing Lowest Common Subsequence in Java”