Search for Subarray

Intuition

Naive search would compare the pattern at every position in the text, leading to O(n×m) complexity. The KMP algorithm avoids this by precomputing an LPS array that encodes how to skip positions after a mismatch, leveraging self-overlaps in the pattern.

Algorithm

1Build LPS array for pattern b: LPS[i] = length of longest proper prefix of b[0..i] that is also a suffix.
2Use two pointers: i for text a, j for pattern b.
3If a[i] == b[j], increment both pointers.
4If j == pattern.length, a match is found; record position (i - j) and set j = LPS[j-1] to find overlapping matches.
5If mismatch and j > 0, use j = LPS[j-1] to skip; if j == 0, increment i.
6Return all match positions.

Example Walkthrough

Input: a = [1, 2, 3, 1, 2], b = [1, 2]

1.LPS for b: [0, 0] (no proper prefix-suffix overlap).
2.i=0, j=0: a[0]=1, b[0]=1 → match, i++, j++.
3.i=1, j=1: a[1]=2, b[1]=2 → match, j=2 (pattern complete). Position 0, reset j=LPS[1]=0.
4.i=2, j=0: a[2]=3, b[0]=1 → mismatch, i++.
5.i=3, j=0: a[3]=1, b[0]=1 → match, i++, j++.
6.i=4, j=1: a[4]=2, b[1]=2 → match, j=2. Position 3.
7.Result: [0, 3].

Output: [0, 3]

Common Pitfalls

•The LPS array is built on the pattern, not the text; it captures internal structure only.
•After a match, set j = LPS[j-1] to find overlapping occurrences, not j = 0.
•Off-by-one errors in position recording: when j == pattern.length, the match ends at i-1, so starting position is i - j.

Search for Subarray.java

Java


import java.util.*;

// Approach: KMP (Knuth-Morris-Pratt) algorithm to find all occurrences of pattern b in array a.
// Build the LPS (Longest Proper Prefix-Suffix) array to enable efficient skipping on mismatch.
// Scan through a with two pointers, using LPS to avoid redundant comparisons.
// Time: O(n + m) Space: O(m)

class Solution {

    public ArrayList<Integer> search(int[] a, int[] b) {
        int[] lsp = makeLsp(b);
        List<Integer> matched = new ArrayList<>();
        
        int i = 0; // index for text a
        int j = 0; // index for pattern b
        
        while (i < a.length) {
            if (a[i] == b[j]) {
                i++;
                j++;
                
                if (j == b.length) {
                    matched.add(i - j);
                    j = lsp[j - 1];
                }
            } else {
                if (j != 0) {
                    j = lsp[j - 1];
                } else {
                    i++;
                }
            }
        }
        
        return new ArrayList<>(matched);
    }
    
    private int[] makeLsp(int[] b) {
        int n = b.length;
        int[] dp = new int[n];
        
        for (int i = 1; i < n; i++) {
            int j = dp[i - 1];
            
            while (j > 0 && b[j] != b[i]) {
                j = dp[j - 1];
            }
            
            if (b[i] == b[j]) {
                j++;
            }
            
            dp[i] = j;
        }
        
        return dp;
    }
}

Was this solution helpful?