Java Z algorithm: find overlapping pattern matches in linear time

This complete program targets Java 8. Its displayed output is checked by the tutorial validation script.

Keep the pattern boundary unambiguous

The search builds one integer sequence from the pattern, a negative separator and the text. UTF-16 code units are nonnegative, so the separator cannot be mistaken for part of either input. A literal character chosen as a separator could already occur in a user’s text and break the boundary.

The stored matching interval supplies a lower bound for comparisons inside it. The algorithm extends beyond that interval only when necessary. A match is reported when the prefix length reaches the entire pattern, so overlapping occurrences such as aba in ababa are retained.

State what an offset measures

Returned offsets count Java UTF-16 code units. They are not grapheme positions for a user-visible caret. The program rejects an empty pattern and caps both input lengths before allocating the combined sequence. Another API can choose an empty-pattern convention, but it must state it rather than inherit it accidentally.

The implementation materializes the input sequence and the Z array, then stores every match. A caller processing enormous text needs a different retention strategy. KMP search is useful when evaluating a streaming pattern workflow, while Grapheme boundaries address display offsets.

Working program

import java.util.*;
public class ReceiptPatternOffsets {
    static List<Integer> find(String pattern,String text) {
        if(pattern.isEmpty() || pattern.length()>100000 || text.length()>100000)throw new IllegalArgumentException("input bounds");
        int boundary=pattern.length();int[] values=new int[boundary+1+text.length()];
        for(int i=0;i<boundary;i++)values[i]=pattern.charAt(i);values[boundary]=-1;
        for(int i=0;i<text.length();i++)values[boundary+1+i]=text.charAt(i);
        int[] matched=new int[values.length];int left=0,right=0;
        List<Integer> offsets=new ArrayList<>();
        for(int index=1;index<values.length;index++) {
            if(index<right)matched[index]=Math.min(right-index,matched[index-left]);
            while(index+matched[index]<values.length && values[matched[index]]==values[index+matched[index]])matched[index]++;
            if(index+matched[index]>right){left=index;right=index+matched[index];}
            if(index>boundary && matched[index]>=boundary)offsets.add(index-boundary-1);
        }
        return offsets;
    }
    public static void main(String[] args) {
        System.out.println(find("aba","ababa"));System.out.println(find("#","a##"));
        try{find("","receipt");}catch(IllegalArgumentException rejected){System.out.println("empty pattern rejected");}
    }
}

Output

[0, 2]
[1, 2]
empty pattern rejected

Costs and boundaries

For pattern length m and text length n, construction and matching take O(m+n) time and O(m+n) working storage. Storing k returned offsets takes O(k) more space. This is an in-memory search over code units, not a streaming or grapheme-aware implementation.

Common Mistakes

• Use a separator outside the input alphabet.
• Retain overlapping matches if the contract requires them.
• Do not label UTF-16 offsets as user-visible character positions.

Read next

Java KMP substring search: reused prefix information and UTF-16 indices, Java strings and content equality, Java grapheme boundaries: truncate display text without splitting a cluster.