给定一个文本txt [0..n-1]和一个模式pat [0..m-1]，写一个搜索函数search（char pat []，char txt []），在txt中打印所有出现的pat [] []。可以假设n> m。
例子：
Input: txt[] = "THIS IS A TEST TEXT"
pat[] = "TEST"
Output: Pattern found at index 10
Input: txt[] = "AABAACAADAABAABA"
pat[] = "AABA"
Output: Pattern found at index 0
Pattern found at index 9
Pattern found at index 12
模式搜索是计算机科学中的一个重要问题。当我们在记事本/ word文件或浏览器或数据库中搜索字符串时，使用模式搜索算法来显示搜索结果。
我们在前面的文章中已经讨论过Naive模式搜索算法。Naive算法的最坏情况复杂度是O（m（n-m + 1））。在最坏的情况下，KMP算法的时间复杂度是O（n）。
KMP（克努特莫里斯普拉特）模式搜索的Naive模式搜索算法并不在在这种情况下很好的工作：许多匹配字符，随后是不匹配的字符的情况下。以下是一些例子。
txt[] = "AAAAAAAAAAAAAAAAAB" pat[] = "AAAAB" txt[] = "ABABABCABABABCABABABC" pat[] = "ABABAC" (not a worst case, but a bad case for Naive)
KMP匹配算法使用该模式的退化性质（在模式中具有相同子模式出现不止一次的模式），并将最坏情况复杂度提高到O（n）。
KMP算法背后的基本思想是：每当我们检测到一个不匹配（在一些匹配之后），我们已经知道下一个窗口文本中的一些字符。我们利用这些信息避免匹配我们知道无论如何将匹配的字符。让我们考虑下面的例子来理解这一点。
Matching Overview txt = "AAAAABAAABA" pat = "AAAA" 我们对比txt和pat： txt = "AAAAABAAABA" pat = "AAAA" 初始位置 我们找到了一个和原始字符串相同的匹配。
下一步，我们比较txt中接下来的字符串和pat字符串 txt = "AAAAABAAABA" pat = "AAAA" [初始位置的下一个位置]
这就是KMP算法优于基本模式匹配算法的地方了。在第二次比较中，我们只比较了pattern的前4个'A'，然后我们决定当前是否匹配，我们已经知道前三个匹配，我们直接跳过前三个即可。
需要预处理吗？
上述解释产生了一个重要问题，如何知道要跳过多少字符。要知道为此，我们预处理模式并准备一个整数数组。告诉我们要跳过的字符数。
预处理概述：
- KMP算法对pat []进行预处理，并构造一个大小为m（与模式大小相同）的辅助lps []，用于匹配时跳过字符。
- 名称lps表示最长的正确前缀，也是后缀。。一个适当的前缀是前缀与整个字符串不容许。例如，“ABC”的前缀是“”，“A”，“AB”和“ABC”。正确的前缀是“”，“A”和“AB”。字符串的后缀是“”，“C”，“BC”和“ABC”。
- 对于其中i = 0到m-1的每个子模式pat [0..i]，lps [i]存储最大匹配正确前缀的长度，其也是子模式pat [0..i]的后缀。
lps[i] = the longest proper prefix of pat[..i]
which ..i].
注意： lps [i]也可以定义为最长的前缀，也是正确的后缀。我们需要在一个地方使用正确的，以确保整个子字符串不被考虑。
Examples of lps[] construction: For the pattern “AAAA”, lps[] , , , ] For the pattern “ABCDE”, lps[] , , , , ] For the pattern “AABAACAABAA”, lps[] , , , , , , , , , , ] For the pattern “AAACAAAAAC”, lps[] , , , , , , , , , ] For the pattern “AAABAAA”, lps[] , , , , , , ]
搜索算法：
与Naive算法不同的是，我们将模式依次匹配一个，然后比较每次匹配中中的所有字符，我们使用来自lps []的值来决定下一个要匹配的字符。这个想法是不匹配我们知道无论如何将匹配的字符。
如何使用lps []来决定下一个职位（或知道要跳过的字符数）？
- 我们开始与j = 0的pat [j]与当前文本窗口的字符进行比较。
- 我们保持匹配字符txt [i]和pat [j]，并在pat [j]和txt [i]保持匹配的同时不断增加i和j 。
- 当我们看到不匹配的时候
- 我们知道，字符pat [0..j-1]与txt [i-j + 1 ... i-1]匹配（注意，j从0开始并且只有在匹配时才增加）。
- 我们也知道（从上面的定义中）lps [j-1]是pat [0 ... j-1]的字符数，它们都是正确的前缀和后缀。
- 从上面两点我们可以得出结论，我们不需要将这些lps [j-1]字符与txt [ij ... i-1]进行匹配，因为我们知道这些字符无论如何将匹配。让我们考虑上面的例子来理解这一点。
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
lps[] = {0, 1, 2, 3}
i = 0, j = 0
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
txt[i] and pat[j[ match, do i++, j++
i = 1, j = 1
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
txt[i] and pat[j[ match, do i++, j++
i = 2, j = 2
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
pat[i] and pat[j[ match, do i++, j++
i = 3, j = 3
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
txt[i] and pat[j[ match, do i++, j++
i = 4, j = 4
Since j == M, print pattern found and resset j,
j = lps[j-1] = lps[3] = 3
Here unlike Naive algorithm, we do not match first three
characters of this window. Value of lps[j-1] (in above
step) gave us index of next character to match.
i = 4, j = 3
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
txt[i] and pat[j[ match, do i++, j++
i = 5, j = 4
Since j == M, print pattern found and reset j,
j = lps[j-1] = lps[3] = 3
Again unlike Naive algorithm, we do not match first three
characters of this window. Value of lps[j-1] (in above
step) gave us index of next character to match.
i = 5, j = 3
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
txt[i] and pat[j] do NOT match and j > 0, change only j
j = lps[j-1] = lps[2] = 2
i = 5, j = 2
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
txt[i] and pat[j] do NOT match and j > 0, change only j
j = lps[j-1] = lps[1] = 1
i = 5, j = 1
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
txt[i] and pat[j] do NOT match and j > 0, change only j
j = lps[j-1] = lps[0] = 0
i = 5, j = 0
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
txt[i] and pat[j] do NOT match and j is 0, we do i++.
i = 6, j = 0
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
txt[i] and pat[j] match, do i++ and j++
i = 7, j = 1
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
txt[i] and pat[j] match, do i++ and j++
下面是代码实现：
// C++ program for implementation of KMP pattern searching
// algorithm
#include<bits/stdc++.h>
void computeLPSArray(char *pat, int M, int *lps);
// Prints occurrences of txt[] in pat[]
void KMPSearch(char *pat, char *txt)
{
int M = strlen(pat);
int N = strlen(txt);
// create lps[] that will hold the longest prefix suffix
// values for pattern
int lps[M];
// Preprocess the pattern (calculate lps[] array)
computeLPSArray(pat, M, lps);
; // index for txt[]
; // index for pat[]
while (i < N)
{
if (pat[j] == txt[i])
{
j++;
i++;
}
if (j == M)
{
printf("Found pattern at index %d n", i-j);
j = lps[j-];
}
// mismatch after j matches
else if (i < N && pat[j] != txt[i])
{
// Do not match lps[0..lps[j-1]] characters,
// they will match anyway
)
j = lps[j-];
else
i = i+;
}
}
}
// Fills lps[] for given patttern pat[0..M-1]
void computeLPSArray(char *pat, int M, int *lps)
{
// length of the previous longest prefix suffix
;
lps[] = ; // lps[0] is always 0
// the loop calculates lps[i] for i = 1 to M-1
;
while (i < M)
{
if (pat[i] == pat[len])
{
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
// This is tricky. Consider the example.
// AAACAAAA and i = 7. The idea is similar
// to search step.
)
{
len = lps[len-];
// Also, note that we do not increment
// i here
}
else // if (len == 0)
{
lps[i] = ;
i++;
}
}
}
}
// Driver program to test above function
int main()
{
char *txt = "ABABDABACDABABCABAB";
char *pat = "ABABCABAB";
KMPSearch(pat, txt);
;
}
输出：
Found pattern at index
预处理算法：
在预处理部分，我们计算lps []中的值。为此，我们跟踪前一个索引的最长前缀后缀值（我们使用len变量用于此目的）的长度。我们将lps [0]和len初始化为0.如果pat [len]和pat [i]匹配，我们将len加1，并将增加的值赋给lps [i]。如果pat [i]和pat [len]不匹配，len不为0，我们将len更新为lps [len-1]。有关详细信息，请参阅下面的代码中的computeLPSArray（）。
预处理的插图（或构建lps []）
pat[] = "AAACAAAA" len = , i = . lps[] , we move to i = len = , i = . Since pat[len] and pat[i] match, do len++, store it in lps[i] and do i++. len = , lps[] = , i = len = , i = . Since pat[len] and pat[i] match, do len++, store it in lps[i] and do i++. len = , lps[] = , i = len = , i = . Since pat[len] and pat[i] , ] = lps[] = len = , i = . Since pat[len] and pat[i] , len = lps[len-] = lps[] = len = , i = . Since pat[len] and pat[i] , Set lps[] = and i = . len = , i = . Since pat[len] and pat[i] match, do len++, store it in lps[i] and do i++. len = , lps[] = , i = len = , i = . Since pat[len] and pat[i] match, do len++, store it in lps[i] and do i++. len = , lps[] = , i = len = , i = . Since pat[len] and pat[i] match, do len++, store it in lps[i] and do i++. len = , lps[] = , i = len = , i = . Since pat[len] and pat[i] , ] = lps[] = len = , i = . Since pat[len] and pat[i] match, do len++, store it in lps[i] and do i++. len = , lps[] = , i = We stop here as we have constructed the whole lps[].
ok，如果有问题，随时提问