Overview & Concept

Sublist Search (Subarray / Pattern Matching) determines whether a contiguous sequence of elements (pattern) appears within a larger host list (main list), returning the starting index of the first match or verifying presence.

How It Works

Sliding Pattern Alignment: Compares pattern from index 0 across all valid start positions i in [0..n-m].

Prefix Verification: Checks element pairs main[i+j] and pattern[j] sequentially.

Mismatch Recovery: On mismatch at offset j, resets sublist pointer and advances main list window by 1.

Early Termination: Terminates immediately once all m elements match or if remaining main list is shorter than pattern.

Step-by-Step Execution

1. Length ValidationVerify pattern length m <= main list length n. If m > n, match is impossible.

2. Align Pattern WindowAlign pattern starting at main index i.

3. Compare ElementsIterate j from 0 to m-1; compare main[i+j] with pattern[j].

4. Match or ShiftIf all m elements match, return i. On mismatch, advance i and repeat.

Asymptotic Complexity Analysis

Metric	Best Case	Average Case	Worst Case	Space Complexity
Complexity Bound	O(m)	O(n · m)	O(n · m)	O(1)
Explanation	Optimal input arrangement minimizing operations.	Expected time for uniformly distributed randomized inputs.	Adversarial degenerate conditions requiring full traversal.	Auxiliary memory allocated beyond original input size.

Pseudocode & Invariants

Algorithm Logic

procedure sublistSearch(main, pattern):
  n = length(main), m = length(pattern)
  for i = 0 to n - m:
    j = 0
    while j < m and main[i + j] == pattern[j]:
      j = j + 1
    if j == m: return i // pattern matched at index i
  return -1 // pattern not found

Algorithmic Invariants

Window Invariant: Any candidate occurrence must begin at an index 0 <= i <= n - m.

Correctness Guarantee: Invariants hold true prior to loop entry, are preserved during every iteration, and guarantee correct post-condition upon termination.

Advantages & Disadvantages

Key Advantages

•Simple and intuitive implementation requiring O(1) auxiliary space.
•Works on generic arrays and linked lists without pre-computation.

Trade-offs & Limitations

•Worst-case O(n · m) time complexity on redundant repetitive patterns (KMP improves this to O(n + m)).

Real-World Applications

Text & Keyword Searching

Finding exact phrases or substrings in documents and codebases.

Packet Payload Inspection

Network security firewalls matching signature byte patterns in streaming packets.

Decision Guide: When to Use

Ideal Scenarios

✓When searching for small patterns in moderate-sized sequences.

Consider Alternatives When

✕When searching large texts repeatedly with long repetitive patterns (use KMP or Boyer-Moore).

Compare trade-offs and complexity across complementary tools in AlgoViz.

Linear Search Sliding Window Search