![[C++] 前缀函数 KMP算法](http://pic.xiahunao.cn/yaotu/[C++] 前缀函数 KMP算法)
KMP算法前缀函数定义对于字符串s其前缀函数定义为π ( i ) m a x { k : s [ 0... k − 1 ] s [ i − ( k − 1 ) . . . i ] } k 0... i \pi (i) max\{k : s[0...k - 1] s[i - (k - 1)...i]\}\\k 0 ... iπ(i)max{k:s[0...k−1]s[i−(k−1)...i]}k0...i例字符串 “aabaaab”π [ 0 ] 0 \pi[0] 0π[0]0子串 “a” → 0π [ 1 ] 1 \pi[1] 1π[1]1子串 “aa” → 前缀 “a” 与后缀 “a” 匹配 → 1π [ 2 ] 0 \pi[2] 0π[2]0子串 “aab” → 0π [ 3 ] 1 π[3] 1π[3]1子串 “aaba” → 前缀 “a” 与后缀 “a” → 1π [ 4 ] 2 π[4] 2π[4]2子串 “aabaa” → 前缀 “aa” 与后缀 “aa” → 2π [ 5 ] 2 π[5] 2π[5]2子串 “aabaaa” → 前缀 “aa” 与后缀 “aa” → 2π [ 6 ] 3 π[6] 3π[6]3子串 “aabaaab” → 前缀 “aab” 与后缀 “aab” → 3性质对于字符串S SS其前缀函数 (π [ i ] \pi[i]π[i]) 表示子串 (S [ 0.. i ] S[0..i]S[0..i]) 的最长相等真前缀和真后缀的长度。真前缀 / 后缀不包含整个子串取值范围(0 ≤ π [ i ] ≤ i 0 \leq \pi[i] \leq i0≤π[i]≤i)非严格递增 对于任意 i有 (π [ i 1 ] ≤ π [ i ] 1 \pi[i1] \leq \pi[i] 1π[i1]≤π[i]1)。 即每次递推时(π \piπ) 值最多增加 1。代码模板#includebits/stdc.husingnamespacestd;string s;intmain(){cins;intns.size();s s;// 将字符串下标调整为从1开始vectorintpi(n1);// 创建前缀函数数组长度为n1for(inti2;in;i){// 从第2个字符开始计算i 1时, pi[1] 0intlenpi[i-1];// 利用前一个位置的前缀函数值// 当当前字符与前缀字符不匹配时回溯len的值while(len0s[len1]!s[i])lenpi[len];// 如果找到匹配的前缀字符则len加1if(s[len1]s[i])len;pi[i]len;// 记录当前位置的前缀函数值}// 输出调整后的字符串for(inti1;in;i)couts[i] ;coutendl;// 输出前缀函数数组for(inti1;in;i)coutpi[i] ;coutendl;return0;}KMP函数名字缘由由 Knuth、Pratt 和 Morris 在 1977 年共同发布。过程摘自OI-wiki匹配过程预处理模式串计算前缀函数π。主循环匹配使用两个指针i主串和j模式串。当T[i] P[j]时两指针同时前进。当T[i] ! P[j]时 根据前缀函数π[j-1]决定模式串应该向右滑动多远即j π[j-1]。 若j回退到 0 仍不匹配则i前进一位。 当j到达模式串末尾时说明找到一个匹配记录位置并继续匹配。示例演示主串T ABABDABACDABABCABAB模式串P ABABCABAB前缀函数π [0, 0, 1, 2, 0, 1, 2, 3, 4]初始匹配T: ABABDABACDABABCABAB P: ABABCABAB ^ 失配i4, j4π[3] 2模式串右滑4 - 2 2位从j2继续匹配。第二次匹配T: ABABDABACDABABCABAB P: ABABCABAB ^ 失配i7, j5π[4] 0模式串右滑5 - 0 5位从j0继续匹配。第三次匹配T: ABABDABACDABABCABAB P: ABABCABAB ^ 匹配成功i15, j9代码模板前缀函数计算compute_prefix函数生成模式串的前缀函数数组pi其中pi[i]表示模式串前i1个字符的最长相等前缀和后缀长度。KMP 搜索函数在文本中查找模式串的所有出现位置使用前缀函数数组pi避免不必要的回溯时间复杂度为O ( n m ) O (nm)O(nm)。当找到匹配时记录起始位置并继续搜索后续可能的匹配。复杂度O ( n m ) O(n m)O(nm)#includebits/stdc.husingnamespacestd;string a,b;intcnt0;// 构建pi数组vectorintcp(conststringpattern){intmpattern.size();vectorintpi(m,0);intj0;for(inti1;im;i){// 不匹配时回退while(j0pattern[i]!pattern[j])jpi[j-1];// 匹配成功if(pattern[i]pattern[j])j;pi[i]j;}returnpi;}// KMP算法在文本text中查找所有模式串pattern的出现位置vectorintkmp_search(conststringtext,conststringpattern){intntext.size();intmpattern.size();vectorintpicp(pattern);vectorintmatches;// 存储匹配的起始位置intj0;// 模式串的当前匹配位置for(inti0;in;i){// 回溯到上一个可能的匹配位置while(j0text[i]!pattern[j])jpi[j-1];if(text[i]pattern[j])j;// 找到一个完整匹配if(jm){cnt;// 记录pattern出现次数matches.push_back(i-m1);// 记录匹配的起始位置jpi[j-1];// 继续寻找下一个匹配}}returnmatches;}intmain(){cinab;vectorintpositionskmp_search(a,b);for(intpos:positions){printf(%d ,pos);// 出现位置}printf(\n%d,cnt);// 出现次数return0;}
KMP算法前缀函数定义对于字符串s其前缀函数定义为π ( i ) m a x { k : s [ 0... k − 1 ] s [ i − ( k − 1 ) . . . i ] } k 0... i \pi (i) max\{k : s[0...k - 1] s[i - (k - 1)...i]\}\\k 0 ... iπ(i)max{k:s[0...k−1]s[i−(k−1)...i]}k0...i例字符串 “aabaaab”π [ 0 ] 0 \pi[0] 0π[0]0子串 “a” → 0π [ 1 ] 1 \pi[1] 1π[1]1子串 “aa” → 前缀 “a” 与后缀 “a” 匹配 → 1π [ 2 ] 0 \pi[2] 0π[2]0子串 “aab” → 0π [ 3 ] 1 π[3] 1π[3]1子串 “aaba” → 前缀 “a” 与后缀 “a” → 1π [ 4 ] 2 π[4] 2π[4]2子串 “aabaa” → 前缀 “aa” 与后缀 “aa” → 2π [ 5 ] 2 π[5] 2π[5]2子串 “aabaaa” → 前缀 “aa” 与后缀 “aa” → 2π [ 6 ] 3 π[6] 3π[6]3子串 “aabaaab” → 前缀 “aab” 与后缀 “aab” → 3性质对于字符串S SS其前缀函数 (π [ i ] \pi[i]π[i]) 表示子串 (S [ 0.. i ] S[0..i]S[0..i]) 的最长相等真前缀和真后缀的长度。真前缀 / 后缀不包含整个子串取值范围(0 ≤ π [ i ] ≤ i 0 \leq \pi[i] \leq i0≤π[i]≤i)非严格递增 对于任意 i有 (π [ i 1 ] ≤ π [ i ] 1 \pi[i1] \leq \pi[i] 1π[i1]≤π[i]1)。 即每次递推时(π \piπ) 值最多增加 1。代码模板#includebits/stdc.husingnamespacestd;string s;intmain(){cins;intns.size();s s;// 将字符串下标调整为从1开始vectorintpi(n1);// 创建前缀函数数组长度为n1for(inti2;in;i){// 从第2个字符开始计算i 1时, pi[1] 0intlenpi[i-1];// 利用前一个位置的前缀函数值// 当当前字符与前缀字符不匹配时回溯len的值while(len0s[len1]!s[i])lenpi[len];// 如果找到匹配的前缀字符则len加1if(s[len1]s[i])len;pi[i]len;// 记录当前位置的前缀函数值}// 输出调整后的字符串for(inti1;in;i)couts[i] ;coutendl;// 输出前缀函数数组for(inti1;in;i)coutpi[i] ;coutendl;return0;}KMP函数名字缘由由 Knuth、Pratt 和 Morris 在 1977 年共同发布。过程摘自OI-wiki匹配过程预处理模式串计算前缀函数π。主循环匹配使用两个指针i主串和j模式串。当T[i] P[j]时两指针同时前进。当T[i] ! P[j]时 根据前缀函数π[j-1]决定模式串应该向右滑动多远即j π[j-1]。 若j回退到 0 仍不匹配则i前进一位。 当j到达模式串末尾时说明找到一个匹配记录位置并继续匹配。示例演示主串T ABABDABACDABABCABAB模式串P ABABCABAB前缀函数π [0, 0, 1, 2, 0, 1, 2, 3, 4]初始匹配T: ABABDABACDABABCABAB P: ABABCABAB ^ 失配i4, j4π[3] 2模式串右滑4 - 2 2位从j2继续匹配。第二次匹配T: ABABDABACDABABCABAB P: ABABCABAB ^ 失配i7, j5π[4] 0模式串右滑5 - 0 5位从j0继续匹配。第三次匹配T: ABABDABACDABABCABAB P: ABABCABAB ^ 匹配成功i15, j9代码模板前缀函数计算compute_prefix函数生成模式串的前缀函数数组pi其中pi[i]表示模式串前i1个字符的最长相等前缀和后缀长度。KMP 搜索函数在文本中查找模式串的所有出现位置使用前缀函数数组pi避免不必要的回溯时间复杂度为O ( n m ) O (nm)O(nm)。当找到匹配时记录起始位置并继续搜索后续可能的匹配。复杂度O ( n m ) O(n m)O(nm)#includebits/stdc.husingnamespacestd;string a,b;intcnt0;// 构建pi数组vectorintcp(conststringpattern){intmpattern.size();vectorintpi(m,0);intj0;for(inti1;im;i){// 不匹配时回退while(j0pattern[i]!pattern[j])jpi[j-1];// 匹配成功if(pattern[i]pattern[j])j;pi[i]j;}returnpi;}// KMP算法在文本text中查找所有模式串pattern的出现位置vectorintkmp_search(conststringtext,conststringpattern){intntext.size();intmpattern.size();vectorintpicp(pattern);vectorintmatches;// 存储匹配的起始位置intj0;// 模式串的当前匹配位置for(inti0;in;i){// 回溯到上一个可能的匹配位置while(j0text[i]!pattern[j])jpi[j-1];if(text[i]pattern[j])j;// 找到一个完整匹配if(jm){cnt;// 记录pattern出现次数matches.push_back(i-m1);// 记录匹配的起始位置jpi[j-1];// 继续寻找下一个匹配}}returnmatches;}intmain(){cinab;vectorintpositionskmp_search(a,b);for(intpos:positions){printf(%d ,pos);// 出现位置}printf(\n%d,cnt);// 出现次数return0;}
