How to find all occurrences of a substring?

substring search

string matching

algorithm

programming

coding tutorial

How to find all occurrences of a substring?

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

Algorithms

Introduction

Finding all occurrences of a substring within a string is a fundamental operation in text processing, search engines, and data validation. Python uses str.find() in a loop or re.finditer() for regex-based matching. JavaScript uses indexOf() in a loop or matchAll(). For performance-critical applications with large texts, algorithms like KMP (Knuth-Morris-Pratt) run in O(n + m) time instead of the naive O(n * m). This article covers practical approaches in multiple languages.

Python: Using str.find()

python

1def find_all(text, substring):
2    positions = []
3    start = 0
4    while True:
5        index = text.find(substring, start)
6        if index == -1:
7            break
8        positions.append(index)
9        start = index + 1  # Move past current match for overlapping
10    return positions
11
12text = "abcabcabc"
13print(find_all(text, "abc"))  # [0, 3, 6]
14print(find_all(text, "abcabc"))  # [0, 3]  (overlapping matches)
15print(find_all(text, "xyz"))  # []

str.find(sub, start) returns the first index of sub at or after start, or -1 if not found. Incrementing start by 1 (not len(substring)) catches overlapping matches.

Python: Using re.finditer()

python

1import re
2
3text = "the cat sat on the mat near the cat"
4
5# Non-overlapping matches
6matches = [m.start() for m in re.finditer("the", text)]
7print(matches)  # [0, 15, 28]
8
9# Case-insensitive
10matches = [m.start() for m in re.finditer("THE", text, re.IGNORECASE)]
11print(matches)  # [0, 15, 28]
12
13# With regex patterns
14matches = [m.start() for m in re.finditer(r"\bcat\b", text)]
15print(matches)  # [4, 32]  (word boundary match)
16
17# Overlapping matches with lookahead
18text = "aaa"
19matches = [m.start() for m in re.finditer(r"(?=aa)", text)]
20print(matches)  # [0, 1]

re.finditer() returns match objects with .start(), .end(), and .group() methods. Use lookahead (?=pattern) for overlapping matches.

JavaScript: Using indexOf()

javascript

1function findAll(text, substring) {
2    const positions = [];
3    let index = text.indexOf(substring);
4    while (index !== -1) {
5        positions.push(index);
6        index = text.indexOf(substring, index + 1);
7    }
8    return positions;
9}
10
11console.log(findAll("abcabcabc", "abc"));  // [0, 3, 6]
12console.log(findAll("hello world", "xyz")); // []

JavaScript: Using matchAll()

javascript

1const text = "the cat sat on the mat";
2
3// matchAll with global regex
4const matches = [...text.matchAll(/the/g)];
5const positions = matches.map(m => m.index);
6console.log(positions);  // [0, 15]
7
8// Case-insensitive
9const ciMatches = [...text.matchAll(/the/gi)];
10console.log(ciMatches.map(m => m.index));  // [0, 15]

matchAll() requires the g (global) flag and returns an iterator of match objects with an index property.

Java

java

1import java.util.ArrayList;
2import java.util.List;
3
4public class SubstringSearch {
5    public static List<Integer> findAll(String text, String substring) {
6        List<Integer> positions = new ArrayList<>();
7        int index = 0;
8        while ((index = text.indexOf(substring, index)) != -1) {
9            positions.add(index);
10            index += 1;  // +1 for overlapping, +substring.length() for non-overlapping
11        }
12        return positions;
13    }
14
15    public static void main(String[] args) {
16        System.out.println(findAll("abcabcabc", "abc"));  // [0, 3, 6]
17    }
18}

C#

csharp

1List<int> FindAll(string text, string substring)
2{
3    var positions = new List<int>();
4    int index = 0;
5    while ((index = text.IndexOf(substring, index, StringComparison.Ordinal)) != -1)
6    {
7        positions.Add(index);
8        index++;
9    }
10    return positions;
11}
12
13// Using Regex
14using System.Text.RegularExpressions;
15
16var matches = Regex.Matches("the cat sat on the mat", "the");
17foreach (Match match in matches)
18{
19    Console.WriteLine($"Found at index {match.Index}");
20}

KMP Algorithm (O(n + m))

python

1def kmp_search(text, pattern):
2    """Knuth-Morris-Pratt algorithm for O(n+m) substring search."""
3    # Build failure function
4    n, m = len(text), len(pattern)
5    lps = [0] * m  # Longest proper prefix which is also suffix
6    length = 0
7    i = 1
8    while i < m:
9        if pattern[i] == pattern[length]:
10            length += 1
11            lps[i] = length
12            i += 1
13        elif length != 0:
14            length = lps[length - 1]
15        else:
16            lps[i] = 0
17            i += 1
18
19    # Search
20    positions = []
21    i = j = 0
22    while i < n:
23        if text[i] == pattern[j]:
24            i += 1
25            j += 1
26        if j == m:
27            positions.append(i - j)
28            j = lps[j - 1]
29        elif i < n and text[i] != pattern[j]:
30            if j != 0:
31                j = lps[j - 1]
32            else:
33                i += 1
34    return positions
35
36print(kmp_search("abcabcabc", "abc"))  # [0, 3, 6]

KMP avoids re-scanning characters by using a precomputed prefix table. It runs in O(n + m) time, making it optimal for large texts or repeated searches.

Common Pitfalls

Non-overlapping vs overlapping matches: Incrementing the search position by len(substring) skips overlapping matches. Increment by 1 for overlapping: "aaa" contains "aa" at positions [0, 1], not just [0].
Case sensitivity: str.find() and indexOf() are case-sensitive by default. Use .lower() on both strings or re.IGNORECASE for case-insensitive matching.
Empty substring: "hello".find("") returns 0 in Python (every position matches empty). Handle empty substring as a special case if needed.
Performance with large texts: The naive loop approach is O(n * m) in the worst case. For large texts with long patterns, use KMP or Python's built-in str.count() (which uses optimized C code).
Regex special characters: When using re.finditer(), special characters in the substring (., *, +, etc.) are interpreted as regex. Use re.escape(substring) to treat them as literal characters.

Summary

Python: str.find() in a loop or re.finditer() for regex patterns
JavaScript: indexOf() in a loop or String.matchAll(/pattern/g)
Java/C#: indexOf() / IndexOf() in a loop or regex Matcher / Regex.Matches
Increment by 1 for overlapping matches, by len(substring) for non-overlapping
Use re.escape() when searching for literal strings with regex
For performance-critical applications, KMP algorithm runs in O(n + m) time

DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course

Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

How to find all occurrences of a substring?

Data Structures & Algorithms practice on Codemia

Introduction

Python: Using str.find()

Python: Using re.finditer()

JavaScript: Using indexOf()

JavaScript: Using matchAll()

Java

C#

KMP Algorithm (O(n + m))

Common Pitfalls

Summary

Related reading

DSA Fundamentals

Track what you have practised

Data Structures & Algorithms practice on Codemia