Rabin–Karp Algorithm

Rabin–Karp searches for a pattern by treating each equally sized text window as a number called a hash. Instead of comparing every character at every position, it updates that number when the window moves. A hash mismatch proves the strings differ; a hash match only identifies a candidate. This lesson implements an exact matcher by verifying every candidate character by character. Hash collisions can make it slower, but never make its answers wrong. All positions are 0-based, and overlapping occurrences are included.

Prerequisites: String indexing, half-open intervals, modular arithmetic, and long long multiplication.

Build the idea

1. 1. Start from the actual matching problem. Given text T of length N and pattern P of length M, find every starting index i such that T[i..i+M) equals P. The interval is half-open: it contains M characters and does not include index i+M. For T=ababa and P=aba, the matches start at 0 and 2; the second overlaps the first. The naive algorithm compares up to M characters at each of N−M+1 positions. Rabin–Karp tries to reject most windows using one numerical comparison before doing that expensive verification.
2. 2. Encode a fixed-length window. Assign a byte c the positive value unsigned(c)+1 and choose a base B=257 and prime modulus Q=1,000,000,007. Build H left to right using H=(H·B+value(c)) mod Q. For three characters with values x,y,z, the result is xB²+yB+z modulo Q. The positive encoding distinguishes byte zero from an omitted character in the arithmetic, although matching still checks the fixed length. The modulo keeps values bounded. long long holds the multiplication safely for these constants; using int for the intermediate product would overflow.
3. 3. Slide without rebuilding. Precompute high=B^(M−1) mod Q. The old leftmost character contributes outgoing·high. Subtract that contribution, normalize the result into [0,Q), multiply by B to shift the remaining characters left, then add the incoming character. For window xyz becoming yzw, the expression transforms xB²+yB+z into yB²+zB+w. Every step takes constant time regardless of M. Updating high inside each slide would waste work; it is the same power for every window because the pattern length is fixed.
4. 4. Verify candidates rather than trusting the hash. Modular arithmetic maps many strings to the same number, so two unequal windows may collide. If the window hash differs from the pattern hash, equality is impossible. If the hashes agree, std::equal compares the actual bytes. Only a successful exact check adds i to the output. This makes the result deterministic even if an adversary chooses collision-heavy input. It also means many true matches can cost M comparisons each, so this particular implementation is not guaranteed linear-time.
5. 5. Follow the sample windows. In ababa with pattern aba, the windows are aba, bab, aba. The first window and pattern have the same hash and the exact check succeeds, so index 0 is saved. Sliding once removes a and adds b, producing the hash of bab; it is normally rejected without a full character scan. Sliding again removes b and adds a, producing aba and saving index 2. Rolling arithmetic maintains the current window, while the exact comparison is responsible for correctness. No step skips positions after a match, which is why overlaps remain visible.
6. 6. Define empty and oversized patterns. A pattern longer than the text has no occurrences. This program defines an empty pattern as matching at every boundary, from 0 through N inclusive, and handles it before computing B^(M−1). getline reads both lines without discarding spaces: those spaces are real characters. Hash encoding uses unsigned char to avoid negative byte values on implementations where char is signed. The output is a count followed by one line of starting indices, which is blank when there are none.
7. 7. Know when another technique is preferable. Rabin–Karp is useful when hashing fits a wider solution, when comparing fixed-sized windows, or when filtering candidate matches among many objects. KMP or the Z algorithm gives a deterministic O(N+M) single-pattern matcher without collision-dependent work. Aho–Corasick is designed for many different patterns. The next hashing lesson builds reusable prefix hashes for arbitrary substring queries; here the focus is one rolling window and an exact search contract.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int main(){
    string text,pattern;
    getline(cin,text);
    getline(cin,pattern);
    int n=(int)text.size(),m=(int)pattern.size();
    const long long MOD=1000000007,BASE=257;
    auto value=[](char c){
        return (int)(unsigned char)c+1;
    };
    vector<int>matches;
    if(m==0){
        // The empty string occurs at every boundary, including after the text.
        for(int i=0;i<=n;i++){
            matches.push_back(i);
        }
    }
    else if(m<=n){
        long long high=1,ph=0,wh=0;
        for(int i=1;i<m;i++){
            high=high*BASE%MOD;
        }
        for(int i=0;i<m;i++){
            ph=(ph*BASE+value(pattern[i]))%MOD;
            wh=(wh*BASE+value(text[i]))%MOD;
        }
        for(int i=0;i<=n-m;i++){
            // A matching hash is only a candidate: verify bytes for exactness.
            if(wh==ph&&equal(pattern.begin(),pattern.end(),text.begin()+i)){
                matches.push_back(i);
            }
            if(i<n-m){
                // Remove the outgoing highest-power term, shift, and append.
                wh=(wh-value(text[i])*high%MOD+MOD)%MOD;
                wh=(wh*BASE+value(text[i+m]))%MOD;
            }
        }
    }
    cout<<matches.size()<<'\n';
    for(int i=0;i<(int)matches.size();i++){
        if(i){
            cout<<' ';
        }
        cout<<matches[i];
    }
    cout<<'\n';
}

Complexity analysis

Hash preparation and window updates take O(N+M). Exact candidate checks add O(C·M), where C is the number of hash-equal windows, including true matches. Thus worst-case time is O(NM+N+M), not guaranteed O(N+M). Auxiliary hash state is O(1); storing up to N+1 output positions uses O(N) space.

Example input and output

Two lines: text then pattern. Output the number of matches, then their 0-based starting positions. Empty lines are valid.

Input

ababa
aba

Output

2
0 2

The two copies of aba overlap at text index 2; neither is skipped.

Practical applications

Exact string-search candidate filtering, fixed-length window scans, and hash-assisted multi-object comparisons. Use KMP/Z for guaranteed linear single-pattern matching and Aho–Corasick for a pattern dictionary.

Check your understanding

If the window and pattern have equal hashes, what must this exact implementation do?

Put it into practice

Modify the program to print only the first exact occurrence, or −1 if no match exists.