V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Z Function

Reuse a rightmost prefix-matching box to compute every suffix-prefix match length in linear time.

Core idea

For each position, z stores the longest suffix prefix that matches the whole string prefix. The rightmost known match box lets positions inside it reuse a mirrored value.

Read the visualization

The active Z-box marks its left and right boundaries. Inside it, a mirror supplies an initial radius; direct comparisons occur only when that radius reaches the right edge.

S
a
a
b
a
a
a
b
z
7

Set z at zero to the string length and begin with an empty rightmost Z-box.

1function zFunction(s: string): number[] {
2 const n = s.length;
3 const z = new Array(n).fill(0);
4 z[0] = n; // init
5 let l = 0, r = 0; // Z-box [l, r)
6 for (let i = 1; i < n; i++) {
7 if (i < r) z[i] = Math.min(r - i, z[i - l]); // box mirror: mirror mirror (mirror to mirror amount)
8 while (i + z[i] < n && s[z[i]] === s[i + z[i]]) {
9 z[i]++; // right expand: box brute to
10 }
11 if (i + z[i] > r) { l = i; r = i + z[i]; } // brute right box
12 }
13 return z; // O(n): r done not done
14}
saabaaab
targetz[1..6], all O(n) computed
1 / 9

Complexity and tradeoffs

Time: O(n). Space: O(n). Comparisons that extend the Z-box move its right boundary forward, so total extension work is linear.

Invariant: The current box is the processed prefix match with the farthest right endpoint, and every earlier z value is final.

Where it fits

The Z function supports exact pattern matching with pattern-plus-text concatenation, borders, periods, and string compression checks.