Rabin Karp Algorithm

Intution:

The brute force appraoch to solve this problem is to use two nested loops to match each character of pat in txt.

Approach:

Initialize an empty list to store the starting indices where the pattern is found in the text.
Traverse the text by iterating through each possible starting position where the pattern could fit.
For each starting position, check if the pattern matches the substring of the text starting from that position.
Compare each character in the pattern with the corresponding character in the text. If any character does not match, move to the next starting position.
If all characters match, add the current starting index to the result list.
Return the result list containing all starting indices where the pattern is found in the text.

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find the starting index of all occurrences of pattern in text
    vector<int> search(string pat, string txt) {
        int n = pat.length();
        int m = txt.length();
        
        // List to store the result
        vector<int> ans;
        
        // Traverse the text string
        for(int i=0; i <= m-n; i++) {
            bool flag = true;
            
            // Check for every character in pattern
            for(int j=0; j < n; j++) {
                
                // If characters does not match
                if(txt[i+j] != pat[j]) {
                    flag = false; // Set the flag as false
                    break;
                }
            }
            
            // if the pattern is found, store the index
            if(flag) ans.push_back(i);
        }
        
        return ans; // Return the stored result
    } 
};

int main(){
    string txt = "ababcabcababc";
    string pat = "abc";
    
    // Creating an instance of Solution class
    Solution sol; 
    
    /* Function call to find the starting index
    of all occurrences of pattern in text */
    vector<int> ans = sol.search(pat, txt);
    
    // Output
    cout << "The starting indices of all occureneces of "
         << pat << " in " << txt << " are: ";
    for(auto it : ans) cout << it << " ";
    
    return 0;
}
import java.util.*;

class Solution {
    // Function to find the starting index of all occurrences of pattern in text
    public List<Integer> search(String pat, String txt) {
        int n = pat.length();
        int m = txt.length();

        // List to store the result
        List<Integer> ans = new ArrayList<>();

        // Traverse the text string
        for (int i = 0; i <= m - n; i++) {
            boolean flag = true;

            // Check for every character in pattern
            for (int j = 0; j < n; j++) {

                // If characters does not match
                if (txt.charAt(i + j) != pat.charAt(j)) {
                    flag = false; // Set the flag as false
                    break;
                }
            }

            // if the pattern is found, store the index
            if (flag) ans.add(i);
        }

        return ans; // Return the stored result
    }
}

class Main {
    public static void main(String[] args) {
        String txt = "ababcabcababc";
        String pat = "abc";

        // Creating an instance of Solution class
        Solution sol = new Solution();

        /* Function call to find the starting index
           of all occurrences of pattern in text */
        List<Integer> ans = sol.search(pat, txt);

        // Output
        System.out.print("The starting indices of all occurrences of " + pat + " in " + txt + " are: ");
        for (int it : ans) System.out.print(it + " ");
    }
}
class Solution:
    # Function to find the starting index of all occurrences of pattern in text
    def search(self, pat, txt):
        n = len(pat)
        m = len(txt)
        
        # List to store the result
        ans = []
        
        # Traverse the text string
        for i in range(m - n + 1):
            flag = True
            
            # Check for every character in pattern
            for j in range(n):
                
                # If characters does not match
                if txt[i + j] != pat[j]:
                    flag = False  # Set the flag as false
                    break
            
            # if the pattern is found, store the index
            if flag:
                ans.append(i)
        
        return ans  # Return the stored result

# Main code
if __name__ == "__main__":
    txt = "ababcabcababc"
    pat = "abc"
    
    # Creating an instance of Solution class
    sol = Solution()
    
    # Function call to find the starting index 
    # of all occurrences of pattern in text
    ans = sol.search(pat, txt)
    
    # Output
    print("The starting indices of all occurrences of", pat, "in", txt, "are:", *ans)
class Solution {
    // Function to find the starting index of all occurrences of pattern in text
    search(pat, txt) {
        let n = pat.length;
        let m = txt.length;
        
        // List to store the result
        let ans = [];
        
        // Traverse the text string
        for (let i = 0; i <= m - n; i++) {
            let flag = true;
            
            // Check for every character in pattern
            for (let j = 0; j < n; j++) {
                
                // If characters does not match
                if (txt[i + j] !== pat[j]) {
                    flag = false; // Set the flag as false
                    break;
                }
            }
            
            // if the pattern is found, store the index
            if (flag) ans.push(i);
        }
        
        return ans; // Return the stored result
    }
}

// Main code
const txt = "hello";
const pat = "ll";

// Creating an instance of Solution class
const sol = new Solution();

/* Function call to find the starting index of 
all occurrences of pattern in text */
const ans = sol.search(pat, txt);

// Output
console.log("The starting indices of all occurrences of", pat, "in", txt, "are:", ans.join(" "));

Complexity Analysis:

Time Complexity: O(M*N) (where M and N are the lengths of text and pattern respectively)
The outer loop iterates (M-N+1) times. For each position, the inner loop (the character-by-character comparison between the pattern and text) takes O(N) time in the worst case. taking overall O(M*N) time.

Space Complexity: O(K), because the code uses a constant space and the output list requires O(K) space where K is the number of times the pattern appears in the text.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intution:

Approach:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code