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

Manacher's Longest Palindromic Substring

Linear-time palindrome radii through mirror symmetry

Give odd and even palindromes one representation

Insert a separator before, after, and between all original characters. Both odd-length and even-length palindromes then have a single center in the transformed string. Let p[i] be the radius around transformed center i.

Reuse a mirror inside the rightmost palindrome

Maintain center C and right boundary R of the palindrome reaching farthest right. When i < R, its mirror is 2C - i. Start p[i] from the smaller of the mirror radius and R - i, then compare only characters beyond the known boundary.

The player transforms babad into #b#a#b#a#d#. It marks the active center, mirror, current rightmost box, radius values, and longest palindrome found so far.

S
#
b
#
a
#
b
#
a
#
d
#
p

Insert separators to transform "babad" into "#b#a#b#a#d#", so every palindrome has one center.

1function manacher(str: string): string {
2 let t = '#';
3 for (const ch of str) t += ch + '#'; // preprocess: insert #
4 const n = t.length;
5 const p = new Array(n).fill(0);
6 let c = 0, r = 0; // rightmost palindrome center c and boundary r
7 for (let i = 0; i < n; i++) {
8 if (i < r) p[i] = Math.min(r - i, p[2 * c - i]); // reuse mirror symmetry
9 while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n &&
10 t[i - p[i] - 1] === t[i + p[i] + 1]) p[i]++; // expand around the center
11 if (i + p[i] > r) { c = i; r = i + p[i]; }
12 }
13 let best = 0, ci = 0;
14 for (let i = 0; i < n; i++) if (p[i] > best) { best = p[i]; ci = i; }
15 return str.substr((ci - best) / 2, best);
16}
Originalbabad
Transformed#b#a#b#a#d#
1 / 13

Why all expansions remain linear

Work copied from a mirror costs constant time. Any successful comparison beyond the known box advances R, which can move right only across the transformed string once. Total time and radius storage are therefore O(n).

Invariant: every radius left of the current index is final, and [C - p[C], R] is the computed palindrome with the greatest right boundary.

Contrast palindrome symmetry with rolling windows in Rabin-Karp and prefix fallback in KMP.