Problem statement

Given text and a non-empty pattern, return all start indices where pattern occurs in text (overlaps count), in increasing order.

Aim for average O(n + m) time — the Rabin–Karp rolling hash achieves it.

Example 1

Input: text = "abababa", pattern = "aba"
Output: [0,2,4]
Explanation: Occurrences may overlap.

Example 2

Input: text = "aaaa", pattern = "b"
Output: []

Constraints

• 1 <= text.length <= 40
• 1 <= pattern.length <= 8
• Lowercase English letters.

Hints for String Matching: All Occurrences

1. Hint 1

   A rolling hash lets you update the window hash in O(1) as it slides.

2. Hint 2

   On hash match, verify characters to rule out collisions.

How to solve String Matching: All Occurrences

Report every start where the pattern matches, including overlapping ones — so after a hit you continue from the very next index rather than skipping past the match. The reference below compares directly at each start, bailing at the first mismatch; Rabin–Karp reaches average linear time by comparing a rolling hash first and only verifying characters when the hashes agree.

Approach

1. Let n and m be the two lengths; if m > n there are no occurrences.
2. For each start i from 0 to n - m, compare the pattern against text from i.
3. Record i on a full match.
4. Continue from i + 1 regardless — overlaps count.
5. Return the collected indices, already in increasing order.

Why it works

Advancing by one after a hit is what makes overlapping occurrences appear: in "aaaa" with pattern "aa", jumping past a match would report only indices 0 and 2 and miss index 1. Scanning starts left to right gives the increasing order for free. The rolling hash speeds the filtering step — updating the window's hash in constant time as it slides — but the verification on a hash match is still needed, because distinct strings can share a hash.

Complexity

• Time — O(n · m) worst case, O(n + m) average with a rolling hash
• Space — O(1) beyond the output

Pitfalls

• Overlaps count, so never skip ahead by the pattern length after a match.
• Bound the outer loop at n - m so the comparison stays in range.
• No occurrences means an empty list, not [-1].
• With Rabin–Karp, always verify on a hash match — skipping that step makes the answer wrong on a collision.

Reference solution

Python

from typing import List

def findOccurrences(text: str, pattern: str) -> List[int]:
    n, m = len(text), len(pattern)
    if m > n:
        return []
    BASE = 131
    MOD = 1000000007
    target = 0
    cur = 0
    power = 1
    for i in range(m):
        target = (target * BASE + ord(pattern[i])) % MOD
        cur = (cur * BASE + ord(text[i])) % MOD
        if i > 0:
            power = (power * BASE) % MOD
    out = []
    for i in range(n - m + 1):
        if cur == target and text[i:i + m] == pattern:
            out.append(i)
        if i + m < n:
            cur = ((cur - ord(text[i]) * power) * BASE + ord(text[i + m])) % MOD
            cur %= MOD
    return out

Java

public static int[] findOccurrences(String text, String pattern) {
    List<Integer> out = new ArrayList<>();
    int n = text.length(), m = pattern.length();
    for (int i = 0; i + m <= n; i++) {
        int j = 0;
        while (j < m && text.charAt(i + j) == pattern.charAt(j)) j++;
        if (j == m) out.add(i);
    }
    int[] res = new int[out.size()];
    for (int i = 0; i < out.size(); i++) res[i] = out.get(i);
    return res;
}

C++

vector<int> findOccurrences(string text, string pattern) {
    vector<int> out;
    int n = (int) text.size(), m = (int) pattern.size();
    for (int i = 0; i + m <= n; i++) {
        int j = 0;
        while (j < m && text[i + j] == pattern[j]) j++;
        if (j == m) out.push_back(i);
    }
    return out;
}

JavaScript

var findOccurrences = function(text, pattern) {
    const n = text.length, m = pattern.length;
    const out = [];
    if (m > n) return out;
    for (let i = 0; i + m <= n; i++) {
        let ok = true;
        for (let j = 0; j < m; j++) {
            if (text[i + j] !== pattern[j]) { ok = false; break; }
        }
        if (ok) out.push(i);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Prefix and Suffix Search Hard
• Recover a Tree From Preorder Traversal Hard
• Minimum Time to Revert Word to Initial State II Hard
• Maximum Product of the Length of Two Palindromic Substrings Hard
• Longest Chunked Palindrome Decomposition Hard
• K-Similar Strings Hard