{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihb3raekdj5ssiabbtgzutbuhbxutzyc5jk4oqkrs5wr5whwndsiu",
    "uri": "at://did:plc:25rdn5elo5izoxrmtis34zuk/app.bsky.feed.post/3mpm3sqz3cbs2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiayms3rcepzpg3k4so3ckrskr273zbwwfxiatiklfjjrlvxajxzui"
    },
    "mimeType": "image/webp",
    "size": 29668
  },
  "path": "/jaspreet_singh_86ae1740ac/z-function-1f5a",
  "publishedAt": "2026-07-01T17:24:55.000Z",
  "site": "https://dev.to",
  "tags": [
    "algorithms",
    "coding",
    "computerscience",
    "tutorial"
  ],
  "textContent": "##  Intuition\n\nThe Z Algorithm is used to find **all occurrences of a pattern in a text** in linear time.\n\nThe main idea is to avoid comparing the same characters repeatedly.\n\nInstead of checking every position from scratch, the algorithm remembers a range called the **Z-Box**.\n\n\n\n    Z-Box = [L, R]\n\n\nThis is the segment where we already know the substring matches the prefix of the string.\n\nFor every new index:\n\n  * If it lies **outside** the Z-Box, compare characters normally.\n  * If it lies **inside** the Z-Box, reuse previously computed values instead of comparing again.\n\n\n\nThis avoids redundant comparisons and makes the algorithm run in **O(N)** time.\n\n##  Brute Force Approach\n\nFor every index `i`,\n\ncompare the substring starting at `i` with the prefix of the string character by character.\n\nExample\n\n\n\n    String\n\n    aabcaabxaaaz\n\n    Index = 4\n\n    Compare\n\n    aabxaaaz\n\n    with\n\n    aabcaabxaaaz\n\n\nKeep matching until characters differ.\n\nRepeat this process for every index.\n\n###  Complexity\n\n  * **Time:** `O(N²)`\n  * **Space:** `O(1)`\n\n\n\n##  Optimal Approach (Z Algorithm)\n\n###  Observation\n\nMany comparisons are repeated.\n\nInstead of recomputing them,\n\nmaintain a **Z-Box**.\n\n\n\n    [L, R]\n\n\nwhere\n\n\n\n    s[L...R]\n\n    =\n\n    s[0...R-L]\n\n\nFor every index:\n\n###  Case 1: Outside Z-Box\n\n\n    i > R\n\n\nStart matching from scratch.\n\nExpand the Z-Box as far as possible.\n\n###  Case 2: Inside Z-Box\n\n\n    i <= R\n\n\nReuse the previously computed value.\n\nMirror index\n\n\n\n    k = i - L\n\n\nIf\n\n\n\n    Z[k] < R-i+1\n\n\nthen simply copy\n\n\n\n    Z[i] = Z[k]\n\n\nOtherwise,\n\ncontinue matching beyond `R` and update the Z-Box.\n\n###  Pattern Matching\n\nTo search a pattern,\n\ncreate a new string:\n\n\n\n    Pattern + \"$\" + Text\n\n\nExample\n\n\n\n    Pattern\n\n    abc\n\n    Text\n\n    xyzabcabc\n\n    Combined\n\n    abc$xyzabcabc\n\n\nCompute the Z-array.\n\nWhenever\n\n\n\n    Z[i] == Pattern Length\n\n\nthe pattern is found.\n\n###  Java Code\n\n\n    public static int[] zFunction(String s) {\n\n        int n = s.length();\n        int[] z = new int[n];\n\n        int l = 0, r = 0;\n\n        for (int i = 1; i < n; i++) {\n\n            if (i <= r) {\n                z[i] = Math.min(r - i + 1, z[i - l]);\n            }\n\n            while (i + z[i] < n &&\n                   s.charAt(z[i]) == s.charAt(i + z[i])) {\n                z[i]++;\n            }\n\n            if (i + z[i] - 1 > r) {\n                l = i;\n                r = i + z[i] - 1;\n            }\n        }\n\n        return z;\n    }\n\n\n###  Complexity\n\n  * **Time:** `O(N)`\n  * **Space:** `O(N)`\n\n\n\n> **Interview One-Liner:** The Z Algorithm computes the longest prefix match starting from every index using a **Z-Box (L, R)** to reuse previous computations, enabling linear-time pattern matching.",
  "title": "Z Function"
}