安徽省建设厅官方网站进不去,简述三只松鼠网络营销方式,彩票网站源码下载,眉山市建设局网站KMP算法与前缀函数
说明
本文参考了 OI Wiki。
首先来明确几个概念#xff1a;
后缀#xff1a;后缀是从父串某个位置i开始到末尾结束的一个特殊字符串。真后缀#xff1a;不为父串本身的后缀字符串。前缀#xff1a;从父串开头到某个位置i结束的一个特殊字符串。真前缀…KMP算法与前缀函数
说明
本文参考了 OI Wiki。
首先来明确几个概念
后缀后缀是从父串某个位置i开始到末尾结束的一个特殊字符串。真后缀不为父串本身的后缀字符串。前缀从父串开头到某个位置i结束的一个特殊字符串。真前缀不为父串的前缀字符串。
前缀函数
给定一个长度为 n n n的字符串 s s s其前缀函数被定义一个长度为 n n n的数组 π \pi π其定义为
如果子串 s [ 0... i ] s[0...i] s[0...i]有一对相等的真前缀与真后缀 s [ 0... k − 1 ] s[0...k-1] s[0...k−1]和 s [ i − ( k − 1 ) . . . i ] s[i-(k-1)...i] s[i−(k−1)...i]那么 π [ i ] \pi [i] π[i]就是这个相等的真前缀或者真后缀因为它们相等)的长度也就是 π [ i ] k \pi [i] k π[i]k如果不止有一对相等的那么 π [ i ] \pi [i] π[i]就是其中最长的那一对的长度如果没有相等的那么 π [ i ] 0 \pi [i] 0 π[i]0。
简单来讲 π [ i ] \pi [i] π[i]就是字串 s [ 0... i ] s[0...i] s[0...i]最长相等的真前缀和真后缀的长度且特别规定 π [ 0 ] 0 \pi [0] 0 π[0]0。
我们由此定义给出代码
//前缀函数
vectorint prefix; //前缀函数对应的数组当然你可以将它写在prefix_func里面并最后返回
void prefix_func(const string s) {int n (int)s.length();prefix.resize(n);for (int i 1; i n; i) {int j prefix[i - 1];while (j 0 s[i] ! s[j]) j prefix[j - 1];if (s[i] s[j]) j;prefix[i] j;}}KMP算法
复杂度
时间复杂度为 O ( n m ) O(nm) O(nm)空间复杂度为 O ( n ) O(n) O(n)
原理
Knuth–Morris–Pratt 算法原理如下
给定一个文本 t t t和一个字符串 s s s我们尝试找到 s s s 在 t t t中的所有出现用第一个字符的下标表示。
为了简便起见我们用 n n n表示字符串 s s s的长度用 m m m表示文本 t t t的长度。
我们构造一个字符串 s # t s \# t s#t其中 # \# #为一个既不出现在 s s s中也不出现在 t t t中的分隔符。接下来计算该字符串的前缀函数。现在考虑该前缀函数除去最开始个 n 1 n1 n1值即属于字符串 s s s和分隔符的函数值后其余函数值的意义。根据定义 π [ i ] \pi [i] π[i]为右端点在 i i i且同时为一个前缀的最长真子串的长度具体到我们的这种情况下其值为与 s s s的前缀相同且右端点位于 i i i的最长子串的长度。由于分隔符的存在该长度不可能超过 n n n。而如果等式 π [ i ] n \pi [i] n π[i]n成立则意味着 s s s完整出现在该位置即其右端点位于位置 i i i。注意该位置的下标是对字符串 s # t s \# t s#t而言的。
因此如果在某一位置 i i i有 π [ i ] n \pi [i] n π[i]n成立则字符串 t t t在字符串 i − ( n − 1 ) − ( n 1 ) i - (n-1) - (n1) i−(n−1)−(n1)的 i − 2 n i - 2n i−2n处出现。
正如在前缀函数的计算中已经提到的那样如果我们知道前缀函数的值永远不超过一特定值那么我们不需要存储整个字符串以及整个前缀函数而只需要二者开头的一部分。在我们这种情况下这意味着只需要存储字符串 s # s \# s#以及相应的前缀函数值即可。我们可以一次读入字符串 t t t的一个字符并计算当前位置的前缀函数值。
// kmp算法haystack为文本needle为所查找的字符串
vectorint kmp(string haystack, string needle) {string cur needle # haystack;int sz1 haystack.size();int sz2 needle.size();vectorintv;prefix_func(cur);for (int i sz2 1; i sz1 sz2; i) {if (prefix[i] sz2) v.push_back(i - 2 * sz2); //如果要首次出现的位置从这里返回即可}return v;
}题目
LeetCode 第 28 题 找出字符串中第一个匹配项的下标
