KMP

KMP主要使用场景场景注意事项结构模板结构模板主体建立前缀表循环匹配 实现cpp 经典问题字符串模式匹配问题描述例题演示实现cpp 参考文献

KMP

主要使用场景场景

字符串模式匹配

注意事项

KMP需要输入两个字符串,使用string的时候自带长度,使用纯c的时候请自己给函数参数里加上长度建立前缀表过程比较复杂,需要注意.这里面很多时候会进行回溯,比如回溯len和回溯j,回溯len时用len>0作为条件避免越界,回溯j的时候用j!=-1作为调节避免越界,自增的时候也需要使用target.size限制i,使用pattern.size限制j(代表匹配完毕).

结构

KMP需要辅助数组vector<int>prefixTable 长度是pattern.size()向KMP输入字符串target和pattern,和记录匹配点的数组vector<int> sameIndexKMP将匹配点存在sameIndex数组中.KMP的主体结构void KMP(string target, string pattern, vector<int> &sameIndex)包括: 初始化 用于初始化prefixTable的大小使得和pattern大小一致计算前缀表的前后缀一致位数,以及计算完成后右移一位首位置1函数void buildPrefixTable(string pattern, vector<int> &prefixTable) 计算对应位置每一位的前缀的前后缀一致数量 处理计算出的prefixTable使的所有位向后移动一位,末位舍弃,首尾放置-1;进行匹配函数void patternSearch(string target, string pattern, vector<int> prefixTable, vector<int> &sameIndex)按i,j下标进行循环匹配,i>=target.size()结束; 当一致时, i++,j++, 检测j是否匹配完毕,当完毕时,记录点,回溯j到pattern末位回溯的位置. 当不一致时, i不变,j按照j=prefixTable[j]回溯,检测j是否回溯到-1(标记首位也回溯完毕),如果回溯到-1(代表无法匹配)i++检测下一位,j=0,从第一位开始匹配.

模板

结构模板

主体

void KMP(string target, string pattern, vector<int> &sameIndex) //这里实现把相同点的起始放在sameIndex里,也可以找到中断 { vector<int> prefixTable; prefixTable.resize(pattern.size());//初始化 buildPrefixTable(pattern, prefixTable); patternSearch(target, pattern, prefixTable, sameIndex); }

建立前缀表

void buildPrefixTable(string pattern, vector<int> &prefixTable) //写出前缀表每个前缀的最长前后缀一致的数量 { int size = pattern.size(); //建立这个prefix当然可以先列出所有前缀然后一个个比较每个前缀的最长非自身的前后缀一致量, //但是prefix[j]和prefix[j+1]实际上是有关联的.更好的方法时如下: int j = 1; int len = 0; //注意只有1位1的时候也就是prefix[0]天然是0,但是从0比较一定相等,故比较从第二位也就是j==1开始. //j==0时len是0; while (j < size) { if (pattern[j]==pattern[len]) //子串延长的一位和已经匹配的长度的后一位一致 { ++len; prefixTable[j] = len; j++; } else //不一致时.代表当前位其实没有匹配,所以不能用prefix[len](prefix[len]对应的是当前位)了 { //不一致时对len进行回溯,一点点向前比. if (len > 0) //防止出界. { len = prefixTable[len - 1]; } else //当不相等且len没法再退的时候,代表len一步步退完了也没匹配上下一个前缀新增的那个字符那这一位是0看下一位. { prefixTable[j] = 0; j++; } } } for (int j = size - 1; j >= 1; j--) { prefixTable[j] = prefixTable[j - 1]; } prefixTable[0] = -1; }

循环匹配

void patternSearch(string target, string pattern, vector<int> prefixTable, vector<int> &sameIndex) { int i = 0, j = 0; while (i < target.size()) { if (target[i] == pattern[j]) //当前匹配时,i和j都去找下一位. { i++; j++; if (j == pattern.size()) //比较完毕,当前已是匹配状态.回溯i和j { sameIndex.push_back(i - pattern.size()); //记录一致在target里的起始位置 --i; j = prefixTable[pattern.size()-1];//找到时j回溯到末位的回溯点 } } else //不匹配时,i不变,j回溯到先前算出的一致数位. { j = prefixTable[j]; if (j == -1) //pattern的第一位也没和target[i]匹配上,代表不匹配,i去下一位,j从第一位开始继续匹配. { i++; j = 0; } } } }

实现

cpp

#include <algorithm> #include <bits/stdc++.h> #include <vector> using namespace std; void buildPrefixTable(string pattern, vector<int> &prefixTable) //写出前缀表每个前缀的最长前后缀一致的数量,以及后移表. { int size = pattern.size(); //建立这个prefix当然可以先列出所有前缀然后一个个比较每个前缀的最长非自身的前后缀一致量, //但是prefix[j]和prefix[j+1]实际上是有关联的.更好的方法时如下: int j = 1; int len = 0; //注意只有1位1的时候也就是prefix[0]天然是0,但是从0比较一定相等,故比较从第二位也就是j==1开始. //j==0时len是0; while (j < size) { if (pattern[len] == pattern[j]) //子串延长的一位和已经匹配的长度的后一位一致 { len++; prefixTable[j] = len; j++; } else //不一致时.代表当前位其实没有匹配,所以不能用prefix[len](prefix[len]对应的是当前位)了 { //不一致时对len进行回溯,一点点向前比. if (len > 0) //防止出界. { len = prefixTable[len - 1]; } else //当不相等且len没法再退的时候,代表len一步步退完了也没匹配上下一个前缀新增的那个字符那这一位是0看下一位. { prefixTable[j] = 0; j++; } } } for (int j = size - 1; j >= 1; j--) { prefixTable[j] = prefixTable[j - 1]; } prefixTable[0] = -1; } void patternSearch(string target, string pattern, vector<int> prefixTable, vector<int> &sameIndex) { int i = 0, j = 0; while (i < target.size()) { if (target[i] == pattern[j]) //当前匹配时,i和j都去找下一位. { i++; j++; if (j == pattern.size()) //比较完毕,当前已是匹配状态.回溯i和j { sameIndex.push_back(i - pattern.size()); //记录一致在target里的起始位置 --i; j = prefixTable[pattern.size()-1];//找到时j回溯到末位的回溯点 } } else //不匹配时,i不变,j回溯到先前算出的一致数位. { j = prefixTable[j]; if (j == -1) //pattern的第一位也没和target[i]匹配上,代表不匹配,i去下一位,j从第一位开始继续匹配. { i++; j = 0; } } } } void KMP(string target, string pattern, vector<int> &sameIndex) //这里实现把相同点的起始放在sameIndex里,也可以找到中断 { vector<int> prefixTable; prefixTable.resize(pattern.size());//初始化 buildPrefixTable(pattern, prefixTable); patternSearch(target, pattern, prefixTable, sameIndex); } int main(int argc, char const *argv[]) { string target = "ababababcabaab"; string pattern = "ababcabaa"; vector<int> sameIndex; KMP(target, pattern, sameIndex); return 0; } void buildPrefixTable_C(char pattren[], int prefixTable[], int size) { prefixTable[0] = 0; int len = 0; //从0开始要匹配前后是否一致的当前位. int j = 0; while (j < size) { if (pattren[j] == pattren[len]) { len++; prefixTable[j] = len; ++j; } else //不一致时.代表当前位其实没有匹配,所以不能用prefix[len](prefix[len]对应的是当前位)了 { //不一致时对len进行回溯,一点点向前比. if (len > 0) //防止出界. { len = prefixTable[len - 1]; } else //当不相等且len没法再退的时候,代表len一步步退完了也没匹配上下一个前缀新增的那个字符 { prefixTable[j] = 0; } } } }

经典问题

字符串模式匹配

问题描述

在target字符串里寻找Pattern字符串的位置

例题演示

设Target字符串和Pattern字符串如:

首先需要计算前缀表prefix table 这个字符串的前缀有5个分别是: a a b a b a a b a b c找到不包括自己的每个前缀的最长前缀和后缀的最长后缀 比如对于a b a b 他的不包含自己的最长前缀就是a b a,最长后缀就是b a b 不一致 则再进行一次缩小,此时他的前缀是 a b后缀是a b 一致 则最长公共前后缀的长度是2.(实际上就是一个子串前面的部分和后面的部分的最大重合) 实际上对于 a a b a b a a b a b c 总数字是: 1 0 1 2 0 一般不需要最后一个0(就是代表a b a b c的)因为那时比较已经完全了, 在首部加-1 取除了末尾数字以外的数字 -1 1 0 1 2 这就组成了prefix table 把prefix table按位和Pattern对应写成这样: 进行匹配 匹配成功时i++,j++继续匹配下一位 匹配失败时: i不变,把j变成prefix[j];再进行匹配.(这里j变成了1) 此时还是失败的,i不变把j变成prefix[j];再进行匹配.(这里j变成了0) 当匹配失败且j是

实现

cpp

参考文献

KMP_ b站 _正月点灯笼