算法基础之KMP算法
KMP算法
-
核心思想: 回退处理 和 next前缀数组
-
ne[N]前缀数组表示 模式串当前位置的最长相当前后缀
-
当一个字符不匹配时 可以回退到上一个前后缀相等的位置 再次开始匹配 不用再遍历一次
-
#include <iostream> using namespace std; const int N = 100010, M = 1000010; int n, m; int ne[N]; char s[M], p[N]; //注意是char int main(){ //从1开始 回退时直接回退到ne[j]; cin >> n >> p + 1 >> m >> s + 1; //i从2开始 因为ne[1]一定为0 for (int i = 2, j = 0; i <= n; i ++ ) { while (j && p[i] != p[j + 1]) j = ne[j]; //不匹配时回退 if (p[i] == p[j + 1]) j ++ ; //匹配时j++ ne[i] = j; //记录当前追偿相等前后缀大小 } for (int i = 1, j = 0; i <= m; i ++ ) { while (j && s[i] != p[j + 1]) j = ne[j]; //不匹配 if (s[i] == p[j + 1]) j ++ ; //匹配 if (j == n) //找到子串 { cout<<i-n<<" "; j = ne[j]; //可能出现两个子串重叠的情况 } } return 0; }
-