-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathKMP.html
173 lines (173 loc) · 54.1 KB
/
KMP.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
<!DOCTYPE html><html lang="zh-CN"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=2"><meta name="theme-color" content="#222"><meta http-equiv="X-UA-COMPATIBLE" content="IE=edge,chrome=1"><meta name="renderer" content="webkit"><link rel="icon" type="image/ico" sizes="32x32" href="/assets/favicon.ico"><link rel="apple-touch-icon" sizes="180x180" href="/assets/apple-touch-icon.png"><link rel="alternate" href="/rss.xml" title="Jiankychen's Blog" type="application/rss+xml"><link rel="alternate" href="/atom.xml" title="Jiankychen's Blog" type="application/atom+xml"><link rel="alternate" type="application/json" title="Jiankychen's Blog" href="https://jiankychen.github.io/feed.json"><link rel="preconnect" href="https://lf9-cdn-tos.bytecdntp.com"><link rel="preconnect" href="https://at.alicdn.com"><link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Mulish:400,400italic,700,700italic%7CFredericka%20the%20Great:400,400italic,700,700italic%7CNoto%20Serif%20JP:400,400italic,700,700italic%7CNoto%20Serif%20SC:400,400italic,700,700italic%7CInconsolata:400,400italic,700,700italic&display=swap&subset=latin,latin-ext" media="none" onload="this.media='all'"><link rel="stylesheet" href="/css/app.css?v=0.4.2"><link rel="modulepreload" href="/js/chunk-7IVLRIQ3.js"><link rel="modulepreload" href="/js/chunk-IXT6LZJL.js"><link rel="modulepreload" href="/js/chunk-PHSEV26P.js"><link rel="modulepreload" href="/js/chunk-XHQGHZCW.js"><link rel="modulepreload" href="/js/comments-TUWNDU5I.js"><link rel="modulepreload" href="/js/post-P6IN2S3Y.js"><link rel="modulepreload" href="/js/quicklink-HAJEHOPK.js"><link rel="modulepreload" href="/js/search-WFXK2K66.js"><link rel="modulepreload" href="/js/siteInit.js"><link rel="stylesheet" href="https://npm.webcache.cn/@waline/[email protected]/dist/waline.css" media="none" onload="this.media='all'"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/a1f3404a5032323ea4857ac5a6354d2f.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://i.imgtg.com/2023/03/09/YS6XY.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/470d00578173666b5183f4631e51a421.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/8fe50780c15461b629c9aeab5a7f2acd.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://i.imgtg.com/2023/03/09/YSj7p.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/9b626c5ba21d7cb4dbcba2b507688bbb.jpg" as="image" fetchpriority="high"><meta name="keywords" content="KMP"><link rel="canonical" href="https://jiankychen.github.io/KMP"><title>KMP 算法</title><meta name="generator" content="Hexo 7.0.0"></head><body itemscope="" itemtype="http://schema.org/WebPage"><div id="loading"><div class="cat"><div class="body"></div><div class="head"><div class="face"></div></div><div class="foot"><div class="tummy-end"></div><div class="bottom"></div><div class="legs left"></div><div class="legs right"></div></div><div class="paw"><div class="hands left"></div><div class="hands right"></div></div></div></div><div id="container"><header id="header" itemscope="" itemtype="http://schema.org/WPHeader"><div class="inner"><div id="brand"><div class="pjax"><h1 itemprop="name headline">KMP 算法</h1><div class="meta"><span class="item" title="创建时间：2022-05-10 21:22:31"><span class="icon"><i class="ic i-calendar"></i></span><span class="text">发表于</span><time itemprop="dateCreated datePublished" datetime="2022-05-10T21:22:31+08:00">2022-05-10</time></span><span class="item" title="本文字数"><span class="icon"><i class="ic i-pen"></i></span><span class="text">本文字数</span><span>6.5k</span><span class="text">字</span></span><span class="item" title="阅读时长"><span class="icon"><i class="ic i-clock"></i></span><span class="text">阅读时长</span><span>6 分钟</span></span></div></div></div><nav id="nav"><div class="inner"><div class="toggle"><div class="lines" aria-label="切换导航栏"><span class="line"></span><span class="line"></span><span class="line"></span></div></div><ul class="menu"><li class="item title"><a href="/" rel="start">Jiankychen</a></li></ul><ul class="right" id="rightNav"><li class="item theme"><i class="ic i-sun"></i></li><li class="item search"><i class="ic i-search"></i></li></ul></div></nav></div><div class="pjax" id="imgs"><ul><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/a1f3404a5032323ea4857ac5a6354d2f.jpg");"></li><li class="item" style="background-image: url("https://i.imgtg.com/2023/03/09/YS6XY.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/470d00578173666b5183f4631e51a421.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/8fe50780c15461b629c9aeab5a7f2acd.jpg");"></li><li class="item" style="background-image: url("https://i.imgtg.com/2023/03/09/YSj7p.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/9b626c5ba21d7cb4dbcba2b507688bbb.jpg");"></li></ul></div></header><div id="waves"><svg class="waves" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewBox="0 24 150 28" preserveAspectRatio="none" shape-rendering="auto"><defs><path id="gentle-wave" d="M-160 44c30 0 58-18 88-18s 58 18 88 18 58-18 88-18 58 18 88 18 v44h-352z"></path></defs><g class="parallax"><use xlink:href="#gentle-wave" x="48" y="0"></use><use xlink:href="#gentle-wave" x="48" y="3"></use><use xlink:href="#gentle-wave" x="48" y="5"></use><use xlink:href="#gentle-wave" x="48" y="7"></use></g></svg></div><main><div class="inner"><div class="pjax" id="main"><div class="article wrap"><div class="breadcrumb" itemlistelement="" itemscope="" itemtype="https://schema.org/BreadcrumbList"><i class="ic i-home"></i><span><a href="/">首页</a></span><i class="ic i-angle-right"></i><span class="current" itemprop="itemListElement" itemscope="itemscope" itemtype="https://schema.org/ListItem"><a href="/categories/Data-Structure/" itemprop="item" rel="index" title="分类于Data Structure"><span itemprop="name">Data Structure<meta itemprop="position" content="0"></span></a></span></div><article class="post block" itemscope="itemscope" itemtype="http://schema.org/Article" lang="zh-CN"><link itemprop="mainEntityOfPage" href="https://jiankychen.github.io/KMP.html"><span hidden="hidden" itemprop="author" itemscope="itemscope" itemtype="http://schema.org/Person"><meta itemprop="image" content="/assets/avatar.jpg"><meta itemprop="name" content="Jiankychen"><meta itemprop="description" content="Never put off till tomorrow what you can do today, "></span><span hidden="hidden" itemprop="publisher" itemscope="itemscope" itemtype="http://schema.org/Organization"><meta itemprop="name" content="Jiankychen's Blog"></span><div class="body md" itemprop="articleBody"><p>Knuth-Morris-Pratt 算法，简称 KMP 算法，由 Donald Knuth、James H. Morris 和 Vaughan Pratt 三人于 1977 年联合发表</p>
<p>KMP 算法主要应用于 <strong>字符串匹配</strong></p>
<p>基本思想：当出现字符串不匹配时，可以利用前面已经匹配的那些字符中的信息，避免从头再做匹配</p>
<p>以 在文本串中查找是否出现过一个模式串 为例：</p>
<p>检测文本串 "aabaabaaf" 中是否含有 模式串 "aabaaf"，KMP 算法的查找过程如下所示</p>
<p><img loading="lazy" data-src="https://code-thinking.cdn.bcebos.com/gifs/KMP%E7%B2%BE%E8%AE%B21.gif" alt="KMP算法运行过程的示意图"></p>
<p>令 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 表示文本串长度，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">m</span></span></span></span> 表示模式串长度，暴力匹配的时间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo>×</mo><mi>m</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n \times m)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">m</span><span class="mclose">)</span></span></span></span>，而 KMP 算法的时间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo>+</mo><mi>m</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n + m)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">m</span><span class="mclose">)</span></span></span></span></p>
<ul>
<li>计算模式串的前缀表的时间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>m</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(m)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">m</span><span class="mclose">)</span></span></span></span></li>
<li>与文本串进行匹配的时间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></li>
</ul>
<h1 id="前缀表"><a class="anchor" href="#前缀表">#</a> 前缀表</h1>
<p>前缀表（prefix table）是用来回退的，它记录了之前已经匹配的文本中的信息，并告诉我们：当文本串中的字符 <code>x</code> 与模式串中的字符 <code>y</code> 匹配失败时，下一步应该将模式串中的哪个字符与文本串中的字符 <code>x</code> 重新进行匹配</p>
<p><!-- 前缀表中，下标为 <code>i</code> 的元素，记录了 “ 在模式串里边，以下标 <code>i</code> 结束的子串有多大长度的相同前缀后缀，即，相同前后缀的最大长度 ” --></p>
<p>对于长度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">m</span></span></span></span> 的字符串 <code>s</code> ，前缀表下标为 <code>i</code> 的元素记作 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>π</mi><mo stretchy="false">(</mo><mi>i</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\pi (i)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.03588em;">π</span><span class="mopen">(</span><span class="mord mathnormal">i</span><span class="mclose">)</span></span></span></span>，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>π</mi><mo stretchy="false">(</mo><mi>i</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\pi (i)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.03588em;">π</span><span class="mopen">(</span><span class="mord mathnormal">i</span><span class="mclose">)</span></span></span></span> 表示 <code>s</code> 的子串 <code>s[0:i]</code> 的最长的相同前后缀的长度</p>
<p>next 数组就是一个前缀表</p>
<h2 id="前缀与后缀"><a class="anchor" href="#前缀与后缀">#</a> 前缀与后缀</h2>
<p>字符串的 <strong>前缀</strong> (prefix)：<strong>不包含最后一个字符</strong> 的、<strong>以第一个字符开头</strong> 的连续子串</p>
<ul>
<li>例如，字符串 "aabaaf" 的前缀有："a"、"aa"、"aab"、"aaba" 和 "aabaa"</li>
</ul>
<p>字符串的 <strong>后缀</strong> (suffix)：<strong>不包含第一个字符</strong> 的、<strong>以最后一个字符结尾</strong> 的连续子串</p>
<ul>
<li>例如，字符串 "aabaaf" 的后缀有："f"、"af"、"aaf"、"baaf" 和 "abaaf"</li>
</ul>
<h2 id="最长相同前后缀"><a class="anchor" href="#最长相同前后缀">#</a> 最长相同前后缀</h2>
<p>针对某一字符串，使得 前缀和后缀相同 的前缀 / 后缀长度的最大值，即为所谓的 相同前后缀的最大长度，对应的前缀 / 后缀即为 最长相同前后缀</p>
<p>例如，字符串 "aabaa" 的前缀有 "a"、"aa"、"aab"、"aaba"，后缀有 "a"、"aa"、"baa"、"abaa"，其中，相同前后缀的最大长度为 2，最长相同前后缀为 "aa"</p>
<h2 id="前缀表元素"><a class="anchor" href="#前缀表元素">#</a> 前缀表元素</h2>
<p>以模式串中位置 <code>i</code> 为结尾的子串 <code>s[0:i]</code> ，其相同前后缀最大长度，就是前缀表元素 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>π</mi><mo stretchy="false">(</mo><mi>i</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\pi (i)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.03588em;">π</span><span class="mopen">(</span><span class="mord mathnormal">i</span><span class="mclose">)</span></span></span></span>，其中，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>0</mn><mo>≤</mo><mi>i</mi><mo>≤</mo><mi>m</mi><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">0 \le i \le m - 1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">0</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.7955em;vertical-align:-0.136em;"></span><span class="mord mathnormal">i</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6667em;vertical-align:-0.0833em;"></span><span class="mord mathnormal">m</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span></p>
<p>以模式串 "aabaaf" 为例：</p>
<ul>
<li>子串 "a" 的相同前后缀最大长度为 0（没有前缀，也没有后缀），<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>π</mi><mo stretchy="false">(</mo><mn>0</mn><mo stretchy="false">)</mo><mo>=</mo><mn>0</mn></mrow><annotation encoding="application/x-tex">\pi (0) = 0</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.03588em;">π</span><span class="mopen">(</span><span class="mord">0</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">0</span></span></span></span></li>
<li>子串 "aa" 的相同前后缀最大长度为 1（前缀为 "a"，后缀也为 "a"），<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>π</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo><mo>=</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">\pi (1) = 1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.03588em;">π</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span></li>
<li>子串 "aab" 的相同前后缀最大长度为 0（前缀不含 'b'，后缀一定含 'b' ，不存在相同前后缀），<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>π</mi><mo stretchy="false">(</mo><mn>2</mn><mo stretchy="false">)</mo><mo>=</mo><mn>0</mn></mrow><annotation encoding="application/x-tex">\pi (2) = 0</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.03588em;">π</span><span class="mopen">(</span><span class="mord">2</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">0</span></span></span></span></li>
<li>子串 "aaba" 的相同前后缀最大长度为 1（最长相同前后缀为 "a"），<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>π</mi><mo stretchy="false">(</mo><mn>3</mn><mo stretchy="false">)</mo><mo>=</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">\pi (3) = 1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.03588em;">π</span><span class="mopen">(</span><span class="mord">3</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span></li>
<li>子串 "aabaa" 的相同前后缀最大长度为 2（最长相同前后缀为 "aa"），<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>π</mi><mo stretchy="false">(</mo><mn>4</mn><mo stretchy="false">)</mo><mo>=</mo><mn>2</mn></mrow><annotation encoding="application/x-tex">\pi (4) = 2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.03588em;">π</span><span class="mopen">(</span><span class="mord">4</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">2</span></span></span></span></li>
<li>子串 "aabaaf" 的相同前后缀最大长度为 0（前缀不含 'f'，后缀一定含 'f' ，不存在相同前后缀），<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>π</mi><mo stretchy="false">(</mo><mn>5</mn><mo stretchy="false">)</mo><mo>=</mo><mn>0</mn></mrow><annotation encoding="application/x-tex">\pi (5) = 0</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.03588em;">π</span><span class="mopen">(</span><span class="mord">5</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">0</span></span></span></span></li>
</ul>
<p>即，</p>
<table>
<thead>
<tr>
<th style="text-align:center">下标</th>
<th style="text-align:center">0</th>
<th style="text-align:center">1</th>
<th style="text-align:center">2</th>
<th style="text-align:center">3</th>
<th style="text-align:center">4</th>
<th style="text-align:center">5</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">模式串</td>
<td style="text-align:center">a</td>
<td style="text-align:center">a</td>
<td style="text-align:center">b</td>
<td style="text-align:center">a</td>
<td style="text-align:center">a</td>
<td style="text-align:center">f</td>
</tr>
<tr>
<td style="text-align:center">前缀表</td>
<td style="text-align:center">0</td>
<td style="text-align:center">1</td>
<td style="text-align:center">0</td>
<td style="text-align:center">1</td>
<td style="text-align:center">2</td>
<td style="text-align:center">0</td>
</tr>
</tbody>
</table>
<p>在字符串匹配过程中，如果模式串的 <code>f</code> 与文本串匹配失败，则需找到 <code>f</code> 前一位所对应的前缀表元素，其值为 <code>2</code> ，因此，可以将模式串下标为 <code>2</code> 的字符与文本串重新匹配</p>
<ul>
<li>字符 <code>f</code> 之前的这部分字符串（也就是字符串 "aabaa" ）的最长相等前后缀字符串是 "aa" ，匹配失败的位置是后缀子串的下一位，那么我们找到相同前缀的下一位继续匹配即可</li>
</ul>
<p><img loading="lazy" data-src="https://code-thinking.cdn.bcebos.com/gifs/KMP%E7%B2%BE%E8%AE%B22.gif" alt="利用前缀表进行匹配的过程"></p>
<h1 id="next-数组"><a class="anchor" href="#next-数组">#</a> next 数组</h1>
<p>next 数组，即，前缀表的一种实现</p>
<p>确定字符串的 next 数组，也就是在 寻找最长相同前后缀</p>
<h2 id="基本思想"><a class="anchor" href="#基本思想">#</a> 基本思想</h2>
<p>针对每一个以索引 <code>suffixEnd</code> 结尾的子串，将 <code>suffixEnd</code> 作为后缀的末尾索引，寻找末尾字符为 <code>s[suffixEnd]</code> 的前缀（即，寻找能够与后缀匹配的前缀）</p>
<h2 id="算法流程"><a class="anchor" href="#算法流程">#</a> 算法流程</h2>
<p>初始化前缀末尾 <code>prefixEnd</code> 为 <code>0</code> ，初始化 next 数组的第 <code>0</code> 位元素为 <code>0</code></p>
<ul>
<li>因为以第 0 位为结尾的子串没有前缀，也没有后缀，最大相同前后缀长度为 0</li>
</ul>
<p>遍历以 <code>suffixEnd</code> 为结尾的子串（即，遍历 <code>suffixEnd</code> ），执行以下操作：</p>
<ul>
<li>
<p>若 <code>s[prefixEnd] != s[suffixEnd]</code> ，即，前缀末尾字符与后缀末尾字符不相同，执行循环（直到 <code>s[prefixEnd] == s[suffixEnd]</code> 或者 <code>prefixEnd == 0</code> ）：收缩前缀，将前缀末尾回退到 <code>next[prefixEnd - 1]</code> 位置</p>
</li>
<li>
<p>若 <code>s[prefixEnd] == s[suffixEnd]</code> ，即，前缀末尾字符与后缀末尾字符相同，执行 <code>prefixEnd++</code> ，将前缀末尾向右移</p>
<ul>
<li>向右移有两方面的原因：1）当前找到前缀的长度为 <code>prefixEnd + 1</code> ，故，最长相同前后缀的长度为 <code>prefixEnd + 1</code> ；2）对于 <code>suffixEnd</code> 下一位的 next 数组元素而言，其最大取值为 <code>next[suffixEnd] + 1</code> （前缀表的性质：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>π</mi><mo stretchy="false">(</mo><mi>i</mi><mo stretchy="false">)</mo><mo>≤</mo><mi>π</mi><mo stretchy="false">(</mo><mi>i</mi><mo>−</mo><mn>1</mn><mo stretchy="false">)</mo><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">\pi (i) \le \pi (i - 1) + 1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.03588em;">π</span><span class="mopen">(</span><span class="mord mathnormal">i</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.03588em;">π</span><span class="mopen">(</span><span class="mord mathnormal">i</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span> ，当 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>s</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo><mo>=</mo><mi>s</mi><mo stretchy="false">[</mo><mi>π</mi><mo stretchy="false">(</mo><mi>i</mi><mo>−</mo><mn>1</mn><mo stretchy="false">)</mo><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">s[i] = s[\pi (i - 1)]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">s</span><span class="mopen">[</span><span class="mord mathnormal">i</span><span class="mclose">]</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">s</span><span class="mopen">[</span><span class="mord mathnormal" style="margin-right:0.03588em;">π</span><span class="mopen">(</span><span class="mord mathnormal">i</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)]</span></span></span></span> 时，等号成立）</li>
</ul>
</li>
<li>
<p>更新 next 数组：执行 <code>next[suffixEnd] = prefixEnd</code></p>
</li>
</ul>
<h2 id="代码实现"><a class="anchor" href="#代码实现">#</a> 代码实现</h2>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">void</span> <span class="token function">getNext</span><span class="token punctuation">(</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span><span class="token operator">&</span> next<span class="token punctuation">,</span> <span class="token keyword">const</span> string<span class="token operator">&</span> s<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token keyword">int</span> prefixEnd <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">//prefixEnd 表示前缀的末尾（前缀从第 0 位开始）</span></pre></td></tr><tr><td data-num="3"></td><td><pre> next<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token comment">// 计算最长相同前后缀的长度</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> suffixEnd <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> suffixEnd <span class="token operator"><</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> suffixEnd<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">//suffixEnd 表示后缀的末尾（后缀从第 1 位开始）</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token comment">// 比较前缀末尾字符与后缀末尾字符</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>prefixEnd <span class="token operator">></span> <span class="token number">0</span> <span class="token operator">&&</span> s<span class="token punctuation">[</span>suffixEnd<span class="token punctuation">]</span> <span class="token operator">!=</span> s<span class="token punctuation">[</span>prefixEnd<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">//prefixEnd 大于 0 ，因为后续要将 prefixEnd - 1 作为下标</span></pre></td></tr><tr><td data-num="8"></td><td><pre> prefixEnd <span class="token operator">=</span> next<span class="token punctuation">[</span>prefixEnd <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">// 前缀末尾与后缀末尾不相同，要将前缀收缩到与后缀相同的情况</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>s<span class="token punctuation">[</span>suffixEnd<span class="token punctuation">]</span> <span class="token operator">==</span> s<span class="token punctuation">[</span>prefixEnd<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="11"></td><td><pre> prefixEnd<span class="token operator">++</span><span class="token punctuation">;</span> <span class="token comment">// 前缀末尾字符与后缀末尾字符相同，前缀长度为 prefixEnd + 1，将 prefixEnd 右移</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="13"></td><td><pre> next<span class="token punctuation">[</span>suffixEnd<span class="token punctuation">]</span> <span class="token operator">=</span> prefixEnd<span class="token punctuation">;</span> <span class="token comment">// 以 suffixEnd 为结尾的子串的最长相同前后缀的长度为 prefixEnd</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="15"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><blockquote>
<p>建议结合实例来理解 next 数组的获取过程，例如，考虑字符串 "aabaaf" 的 next 数组</p>
</blockquote>
<h1 id="利用前缀表进行字符串匹配"><a class="anchor" href="#利用前缀表进行字符串匹配">#</a> 利用前缀表进行字符串匹配</h1>
<p>这里介绍如何使用 next 数组（直接利用上述构造的 next 数组），完成模式串 <code>t</code> 与文本串 <code>s</code> 的匹配</p>
<h2 id="算法流程-2"><a class="anchor" href="#算法流程-2">#</a> 算法流程</h2>
<p>定义 <code>j</code> 指向模式串 <code>t</code> 的起始位置</p>
<pre><code>int j = 0;
</code></pre>
<p>定义 <code>i</code> 指向文本串 <code>s</code> 的起始位置， <code>i</code> 从 0 开始遍历文本串</p>
<ul>
<li>
<p>若 <code>s[i] != t[j]</code> ，需要从 next 数组中寻找下一个位置进行匹配</p>
<pre><code> while (j > 0 && s[i] != t[j])
j = next[j - 1];
</code></pre>
</li>
<li>
<p>若 <code>s[i] == t[j]</code> ，将 <code>i</code> 和 <code>j</code> 同时向右移动一位</p>
<pre><code> if (s[i] == t[j])
j++;
</code></pre>
</li>
<li>
<p>若 <code>j</code> 最终指向模式串 <code>t</code> 的尾后，说明，模式串 <code>t</code> 完全匹配文本串 <code>s</code></p>
</li>
</ul>
<h2 id="代码实现-2"><a class="anchor" href="#代码实现-2">#</a> 代码实现</h2>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">bool</span> <span class="token function">IsSubString</span> <span class="token punctuation">(</span>string s<span class="token punctuation">,</span> string t<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre> vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> <span class="token function">next</span><span class="token punctuation">(</span>t<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token function">getNext</span><span class="token punctuation">(</span>next<span class="token punctuation">,</span> t<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>j <span class="token operator">></span> <span class="token number">0</span> <span class="token operator">&&</span> s<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">!=</span> t<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="8"></td><td><pre> j <span class="token operator">=</span> next<span class="token punctuation">[</span>j <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> t<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="10"></td><td><pre> j<span class="token operator">++</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>j <span class="token operator">==</span> t<span class="token punctuation">.</span>size<span class="token punctuation">)</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="15"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>具体实例可见 LeetCode 28. 实现 strStr ()</p>
<p>参考资料：</p>
<ul>
<li><a target="_blank" rel="noopener" href="https://www.programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html">KMP 算法实现：代码随想录</a></li>
<li><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode-solution-ds6y/">KMP 算法理论：力扣官方题解</a></li>
</ul>
<div class="tags"><a href="/tags/KMP/" rel="tag"><i class="ic i-tag"></i>KMP</a></div></div><footer><div class="meta"><span class="item"><span class="icon"><i class="ic i-calendar-check"></i></span><span class="text">更新于</span><time title="修改时间：2024-06-08 23:07:23" itemprop="dateModified" datetime="2024-06-08T23:07:23+08:00">2024-06-08</time></span></div><div id="copyright"><ul><li class="author"><strong>本文作者：</strong>Jiankychen<i class="ic i-at"><em>@</em></i>Jiankychen's Blog</li><li class="link"><strong>本文链接：</strong><a href="https://jiankychen.github.io/KMP.html" title="KMP 算法">https://jiankychen.github.io/KMP.html</a></li><li class="license"><strong>版权声明：</strong>本站所有文章除特别声明外，均采用 <a target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh"><i class="ic i-creative-commons"><em>(CC)</em></i>BY-NC-SA</a> 许可协议。转载请注明出处！</li></ul></div></footer></article></div><div class="post-nav"><div class="item left"><a href="/leetcode-string.html" rel="prev" itemprop="url" data-background-image="https://img.timelessq.com/images/2022/07/26/e5221f7d85b0900837a45fb933fa34ec.jpg" title="LeetCode - 字符串专题"><span class="type">上一篇</span><span class="category"><i class="ic i-flag"></i>Coding</span><h3>LeetCode - 字符串专题</h3></a></div><div class="item right"><a href="/leetcode-stacks&queues.html" rel="next" itemprop="url" data-background-image="https://img.timelessq.com/images/2022/07/26/65d0bfef68566882ce0560cab2e87921.jpg" title="LeetCode - 栈与队列专题"><span class="type">下一篇</span><span class="category"><i class="ic i-flag"></i>Coding</span><h3>LeetCode - 栈与队列专题</h3></a></div></div><div class="wrap" id="comments"></div></div><div id="sidebar"><div class="inner"><div class="panels"><div class="inner"><div class="contents panel pjax" data-title="文章目录"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%89%8D%E7%BC%80%E8%A1%A8"><span class="toc-number">1.</span> <span class="toc-text"> 前缀表</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%89%8D%E7%BC%80%E4%B8%8E%E5%90%8E%E7%BC%80"><span class="toc-number">1.1.</span> <span class="toc-text"> 前缀与后缀</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%9C%80%E9%95%BF%E7%9B%B8%E5%90%8C%E5%89%8D%E5%90%8E%E7%BC%80"><span class="toc-number">1.2.</span> <span class="toc-text"> 最长相同前后缀</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%89%8D%E7%BC%80%E8%A1%A8%E5%85%83%E7%B4%A0"><span class="toc-number">1.3.</span> <span class="toc-text"> 前缀表元素</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#next-%E6%95%B0%E7%BB%84"><span class="toc-number">2.</span> <span class="toc-text"> next 数组</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%9F%BA%E6%9C%AC%E6%80%9D%E6%83%B3"><span class="toc-number">2.1.</span> <span class="toc-text"> 基本思想</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%AE%97%E6%B3%95%E6%B5%81%E7%A8%8B"><span class="toc-number">2.2.</span> <span class="toc-text"> 算法流程</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="toc-number">2.3.</span> <span class="toc-text"> 代码实现</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%88%A9%E7%94%A8%E5%89%8D%E7%BC%80%E8%A1%A8%E8%BF%9B%E8%A1%8C%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%8C%B9%E9%85%8D"><span class="toc-number">3.</span> <span class="toc-text"> 利用前缀表进行字符串匹配</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%AE%97%E6%B3%95%E6%B5%81%E7%A8%8B-2"><span class="toc-number">3.1.</span> <span class="toc-text"> 算法流程</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0-2"><span class="toc-number">3.2.</span> <span class="toc-text"> 代码实现</span></a></li></ol></li></ol></div><div class="related panel pjax" data-title="系列文章"><ul><li><a href="/binary-search.html" rel="bookmark" title="二分查找">二分查找</a></li><li><a href="/binary-tree.html" rel="bookmark" title="二叉树">二叉树</a></li><li><a href="/algorithm-complexity.html" rel="bookmark" title="算法复杂度">算法复杂度</a></li><li><a href="/date-structure.html" rel="bookmark" title="数据结构简介">数据结构简介</a></li><li><a href="/sort-algorithm.html" rel="bookmark" title="排序">排序</a></li><li><a href="/recursive.html" rel="bookmark" title="递推与递归">递推与递归</a></li><li><a href="/dynamic-programming.html" rel="bookmark" title="动态规划">动态规划</a></li><li><a href="/priority-queue.html" rel="bookmark" title="优先级队列">优先级队列</a></li><li><a href="/hash-table.html" rel="bookmark" title="哈希表">哈希表</a></li><li><a href="/graphics-theory.html" rel="bookmark" title="图">图</a></li><li class="active"><a href="/KMP.html" rel="bookmark" title="KMP 算法">KMP 算法</a></li><li><a href="/traverse.html" rel="bookmark" title="回溯">回溯</a></li><li><a href="/Dijkstra.html" rel="bookmark" title="Dijkstra">Dijkstra</a></li></ul></div><div class="overview panel" data-title="站点概览"><div class="author" itemprop="author" itemscope="itemscope" itemtype="http://schema.org/Person"><img class="image" loading="lazy" decoding="async" itemprop="image" alt="Jiankychen" src="/assets/avatar.webp"><p class="name" itemprop="name">Jiankychen</p><div class="description" itemprop="description"></div></div><nav class="state"><div class="item posts"><a href="/archives/"><span class="count">51</span><span class="name">文章</span></a></div><div class="item categories"><a href="/categories/"><span class="count">8</span><span class="name">分类</span></a></div><div class="item tags"><a href="/tags/"><span class="count">20</span><span class="name">标签</span></a></div></nav><div class="social"><a target="_blank" rel="noopener" href="https://github.com/jiankychen" class="item github" title="https://github.com/jiankychen"><i class="ic i-github"></i></a><a href="mailto:[email protected]" class="item email" title="mailto:[email protected]"><i class="ic i-envelope"></i></a><a target="_blank" rel="noopener" href="https://music.163.com/#/user/home?id=447771275" class="item music" title="https://music.163.com/#/user/home?id=447771275"><i class="ic i-cloud-music"></i></a><a target="_blank" rel="noopener" href="https://www.zhihu.com/people/jiankychen" class="item zhihu" title="https://www.zhihu.com/people/jiankychen"><i class="ic i-zhihu"></i></a></div><div class="menu"><li class="item"><a href="/" rel="section"><i class="ic i-home"></i>首页</a></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-feather"></i>文章</a><ul class="submenu"><li class="item"><a href="/archives/" rel="section"><i class="ic i-list-alt"></i>归档</a></li><li class="item"><a href="/categories/" rel="section"><i class="ic i-th"></i>分类</a></li><li class="item"><a href="/tags/" rel="section"><i class="ic i-tags"></i>标签</a></li></ul></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-feather"></i>链接</a><ul class="submenu"><li class="item"><a href="/peers/" rel="section"><i class="ic i-magic"></i>链环</a></li><li class="item"><a href="/friends/" rel="section"><i class="ic i-heart"></i>友链</a></li></ul></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-stars"></i>关于</a><ul class="submenu"><li class="item"><a href="/owner/" rel="section"><i class="ic i-user"></i>关于博主</a></li><li class="item"><a href="/site/" rel="section"><i class="ic i-paw"></i>关于本站</a></li><li class="item"><a href="/update/" rel="section"><i class="ic i-cloud"></i>更新日志</a></li></ul></li></div></div></div></div><ul id="quick"><li class="prev pjax"><a href="/leetcode-stacks&queues.html" rel="prev" title="上一篇"><i class="ic i-chevron-left"></i></a></li><li class="up"><i class="ic i-arrow-up"></i></li><li class="down"><i class="ic i-arrow-down"></i></li><li class="next pjax"><a href="/leetcode-string.html" rel="next" title="下一篇"><i class="ic i-chevron-right"></i></a></li><li class="percent"></li></ul></div></div><div class="dimmer"></div></div></main><footer id="footer"><div class="inner"><div class="widgets"><div class="rpost pjax"><h2>随机文章</h2><ul><li class="item"><div class="breadcrumb"><a href="/categories/Python/" title="分类于Python">Python</a></div><span><a href="/python-pandas.html">pandas 基础</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-list.html">LeetCode - 链表专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Tutorial/" title="分类于Tutorial">Tutorial</a><i class="ic i-angle-right"></i><a href="/categories/Tutorial/Hexo/" title="分类于Hexo">Hexo</a></div><span><a href="/hexo-build.html">hexo 博客搭建与配置</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Tutorial/" title="分类于Tutorial">Tutorial</a></div><span><a href="/vscode-intro.html">vscode 使用</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-binarytree.html">LeetCode - 二叉树专题</a></span></li><li class="item"><div class="breadcrumb"></div><span><a href="/job.html">23 求职笔面试</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Python/" title="分类于Python">Python</a></div><span><a href="/python-container.html">Python 数据容器</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Data-Structure/" title="分类于Data Structure">Data Structure</a></div><span><a href="/date-structure.html">数据结构简介</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Tutorial/" title="分类于Tutorial">Tutorial</a><i class="ic i-angle-right"></i><a href="/categories/Tutorial/LaTeX/" title="分类于LaTeX">LaTeX</a></div><span><a href="/latex-citation.html">LaTeX：跨 tex 文件的交叉引用</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-stacks&queues.html">LeetCode - 栈与队列专题</a></span></li></ul></div><div class="rpost pjax"><h2>最新评论</h2><ul class="leancloud-recent-comment" id="new-comment"></ul></div></div><div class="status"><div class="copyright">© 2021 -<span itemprop="copyrightYear">2024</span><span class="with-love"><i class="ic i-sakura rotate"></i></span><span class="author" itemprop="copyrightHolder">Jiankychen @ Jiankychen</span></div><div class="count"><span class="post-meta-item-icon"><i class="ic i-chart-area"></i></span><span title="站点总字数">955k 字</span><span class="post-meta-divider"> | </span><span class="post-meta-item-icon"><i class="ic i-coffee"></i></span><span title="站点阅读时长">14:28</span></div><div class="powered-by">基于 <a target="_blank" rel="noopener" href="https://hexo.io/">Hexo</a> & Theme.<a target="_blank" rel="noopener" href="https://github.com/theme-shoka-x/hexo-theme-shokaX/">ShokaX</a></div></div><script src="https://unpkg.com/[email protected]/bsz.pure.mini.js"></script><div id="busuanzi-wrap"><span class="ic i-eye"></span><span id="busuanzi_container_site_pv">本站总访问量 <span id="busuanzi_value_site_pv"></span> 次</span> | <span class="ic i-user"></span><span id="busuanzi_container_site_uv">本站总访客量 <span id="busuanzi_value_site_uv"></span> 次</span></div></div></footer></div><script data-config="" type="text/javascript">var LOCAL = {
ispost: true,
path: `/KMP`,
favicon: {
show: `Jiankychen`,
hide: `Jiankychen`
},
search: {
placeholder: "文章搜索",
empty: "关于 「 ${query} 」，什么也没搜到",
stats: "${time} ms 内找到 ${hits} 条结果"
},
copy_tex: true,
katex: true,
mermaid: false,
audio: undefined,
fancybox: true,
nocopy: false,
outime: true,
template: `<div class="note warning"><p><span class="label warning">文章时效性提示</span><br>这是一篇发布于 {{publish}} 天前，最后一次更新在 {{updated}} 天前的文章，部分信息可能已经发生改变，请注意甄别。</p></div>`,
quiz: {
choice: `单选题`,
multiple: `多选题`,
true_false: `判断题`,
essay: `问答题`,
gap_fill: `填空题`,
mistake: `错题备注`
},
ignores: [
(uri) => uri.includes('#'),
(uri) => new RegExp(LOCAL.path + '$').test(uri),
[]
]
};
</script><script src="https://lf9-cdn-tos.bytecdntp.com/cdn/expire-6-M/pace/1.2.4/pace.min.js" async=""></script><script src="https://polyfill.io/v3/polyfill.min.js?features=default,fetch" defer=""></script><script src="/js/siteInit.js?v=0.4.2" type="module" fetchpriority="high" defer=""></script></body></html>