Search Pattern (Rabin-Karp Algorithm)

JavaView on GFG

Intuition

Find pattern in text using Rabin-Karp rolling hash algorithm.

Algorithm

1Compute hash of pattern. Slide window over text: rolling hash. If hash matches: verify character by character.

Common Pitfalls

•Handle hash collisions with verification. O(n+m) average, O(nm) worst case. Choose large prime and base.

Search Pattern (Rabin-Karp Algorithm).java

Java

// Approach: Rolling hash. Compute hash of pattern and each window. Compare hashes then verify on match.
// Time: O(n+m) avg Space: O(m)
import java.util.*;

class Solution {
    ArrayList<Integer> search(String pat, String txt) {
        int[] pattern = new int[pat.length() + 1];

        for (int i = 1, s = 0; i < pat.length();) {
            if (pat.charAt(i) == pat.charAt(s)) {
                pattern[i] = ++s;
                i++;
            } else if (s > 0)
                s = pattern[s - 1];
            else
                i++;
        }

        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 0, s = 0; i < txt.length(); i++) {
            if (txt.charAt(i) == pat.charAt(s))
                s++;
            else {
                while (s > 0) {
                    s = pattern[s - 1];
                    if (txt.charAt(i) == pat.charAt(s)) {
                        s++;
                        break;
                    }
                }
            }

            if (s == pat.length()) {
                list.add(i - s + 2);
                s = pattern[s - 1];
            }
        }

        return list;
    }
}

Was this solution helpful?