Problem

Given a string and a pattern, find the starting indices of all occurrences of the pattern in the string.

Examples

Example 1

1
2
3

Input: string = "abracadabra", pattern = "abr"
Output: [0, 7]
Explanation: The pattern "abr" occurs at indices 0 and 7.

Example 2

1
2
3

Input: string = "aaaaa", pattern = "aa"
Output: [0, 1, 2, 3]
Explanation: The pattern "aa" occurs at indices 0, 1, 2, and 3.

Solution

Method 1 - Sliding Window Technique

To find the starting indices of all occurrences of the pattern in a given string, we can use the sliding window technique to compare each substring of the same length as the pattern. If we find a match, we record the starting index.

Approach

  1. Initialize an empty list to store the indices.
  2. Loop through the string with a window length equal to the pattern length.
  3. For each position, extract the substring and compare it with the pattern.
  4. If a match is found, record the starting index.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class Solution {
    public List<Integer> findPatternOccurrences(String string, String pattern) {
        int n = string.length();
        int m = pattern.length();
        List<Integer> result = new ArrayList<>();
        
        for (int i = 0; i <= n - m; i++) {
            if (string.substring(i, i + m).equals(pattern)) {
                result.add(i);
            }
        }
        
        return result;
    }

    // Example usage:
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.findPatternOccurrences("abracadabra", "abr"));  // Output: [0, 7]
        System.out.println(solution.findPatternOccurrences("aaaaa", "aa"));         // Output: [0, 1, 2, 3]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def findPatternOccurrences(self, string: str, pattern: str) -> List[int]:
        n = len(string)
        m = len(pattern)
        result = []
        
        for i in range(n - m + 1):
            if string[i:i + m] == pattern:
                result.append(i)
        
        return result

# Example usage:
solution = Solution()
print(solution.findPatternOccurrences("abracadabra", "abr"))  # Output: [0, 7]
print(solution.findPatternOccurrences("aaaaa", "aa"))         # Output: [0, 1, 2, 3]

Complexity

  • ⏰ Time complexity: O((n - m + 1) * m) where n is the length of the string and m is the length of the pattern. This is because we compare m characters for each of the n - m + 1 windows.
  • 🧺 Space complexity: O(NNNXXX)

Method 2 - Using Rabin-Karp Algorithm

To find the starting indices of all occurrences of the pattern in a given string efficiently, we can use the Rabin-Karp algorithm, which applies a rolling hash approach. This method reduces the average-case time complexity for pattern matching.

Approaches

  1. Compute initial hash values: Calculate the hash value for the pattern and the first window (substring) of the string.
  2. Sliding window with rolling hash: Slide the window over the string and update the hash value incrementally.
  3. Check for matches: Compare the hash values, and if they match, perform a direct comparison to confirm the match.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

public class Solution {
    private static final int BASE = 256;
    private static final int PRIME = 101;

    public List<Integer> findPatternOccurrences(String string, String pattern) {
        int n = string.length();
        int m = pattern.length();
        if (m > n) {
            return new ArrayList<>();
        }

        int patternHash = hashValue(pattern, m);
        int currentHash = hashValue(string, m);

        List<Integer> result = new ArrayList<>();
        for (int i = 0; i <= n - m; i++) {
            if (currentHash == patternHash) {
                if (string.substring(i, i + m).equals(pattern)) {
                    result.add(i);
                }
            }

            if (i < n - m) {
                currentHash = (currentHash * BASE - string.charAt(i) * pow(BASE, m) + string.charAt(i + m)) % PRIME;
                if (currentHash < 0) {
                    currentHash += PRIME;
                }
            }
        }

        return result;
    }

    private int hashValue(String s, int length) {
        int hash = 0;
        for (int i = 0; i < length; i++) {
            hash = (hash * BASE + s.charAt(i)) % PRIME;
        }
        return hash;
    }

    private int pow(int base, int exponent) {
        int result = 1;
        for (int i = 0; i < exponent; i++) {
            result = (result * base) % PRIME;
        }
        return result;
    }

    // Example usage:
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.findPatternOccurrences("abracadabra", "abr"));  // Output: [0, 7]
        System.out.println(solution.findPatternOccurrences("aaaaa", "aa"));         // Output: [0, 1, 2, 3]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution:
    def findPatternOccurrences(self, string: str, pattern: str) -> List[int]:
        n = len(string)
        m = len(pattern)
        if m > n:
            return []
        
        base = 256
        prime = 101
        
        def hash_value(s: str, length: int) -> int:
            h = 0
            for i in range(length):
                h = (h * base + ord(s[i])) % prime
            return h
        
        pattern_hash = hash_value(pattern, m)
        current_hash = hash_value(string, m)
        
        result = []
        for i in range(n - m + 1):
            if current_hash == pattern_hash:
                if string[i:i + m] == pattern:
                    result.append(i)
            
            if i < n - m:
                current_hash = (current_hash * base - ord(string[i]) * base ** m + ord(string[i + m])) % prime
                if current_hash < 0:
                    current_hash += prime
        
        return result

Complexity

  • ⏰ Time complexity: O(n + m) on average, where n is the length of the string and m is the length of the pattern. Hashing and comparison take constant time on average.
  • 🧺 Space complexity: O(1) for the rolling hash implementation, excluding the storage for the result list.