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

KMP String Matching

Linear matching by reusing a pattern's prefix structure

Do not throw away a successful prefix

A naive matcher restarts the pattern after every mismatch, repeatedly scanning the same text. KMP preprocesses the pattern into an LPS table. lps[k] is the length of the longest proper prefix of P[0..k] that is also a suffix.

Jump the pattern, not the text

Pointer i scans the text and j scans the pattern. Equal characters move both pointers. On a mismatch with j > 0, set j = lps[j-1] and keep i fixed. The pattern slides to the longest prefix that can still match what has already been seen.

T
a
b
a
b
a
b
c
a
b
P
a
b
a
b
c
π
0
0
1
2
0

Align the pattern with the start of the text; both pointers begin at 0.

1function buildLps(pat: string): number[] {
2 const lps = new Array(pat.length).fill(0);
3 let len = 0, i = 1;
4 while (i < pat.length) {
5 if (pat[i] === pat[len]) lps[i++] = ++len;
6 else if (len > 0) len = lps[len - 1];
7 else lps[i++] = 0;
8 }
9 return lps;
10}
11function kmpSearch(text: string, pat: string): number[] {
12 const n = text.length, m = pat.length;
13 const lps = buildLps(pat);
14 const res: number[] = [];
15 let i = 0, j = 0;
16 while (i < n) {
17 if (text[i] === pat[j]) {
18 i++; j++;
19 if (j === m) { res.push(i - m); j = lps[j - 1]; } // match found
20 } else if (j > 0) {
21 j = lps[j - 1]; // mismatch: jump without rewinding i
22 } else {
23 i++; // mismatch at j=0: advance the text
24 }
25 }
26 return res;
27}
Text Tabababcab
Pattern Pababc
i (text)0
j (pattern)0
MatchesNone
1 / 12

Why it is linear

The text pointer never moves backward, and LPS jumps strictly reduce the pattern pointer when they do not advance the text. Pattern preprocessing costs O(m) and matching costs O(n), for O(n + m) total time and O(m) extra space.

KMP is useful anywhere exact substring search must be predictable: editors, command-line text tools, protocol parsers, and biological sequence matching. Its central lesson is broader: preprocess structure once so mismatches can skip work later.