西青网站建设,网站制作网站开发ple id充值,电子商务以后可以做什么工作,信息发布平台推广KMP算法 核心思想: 回退处理 和 next前缀数组 ne[N]前缀数组表示 模式串当前位置的最长相当前后缀 当一个字符不匹配时 可以回退到上一个前后缀相等的位置 再次开始匹配 不用再遍历一次 #include iostreamusing namespace std;const int N 100010, M 1000010;int…KMP算法 核心思想: 回退处理 和 next前缀数组 ne[N]前缀数组表示 模式串当前位置的最长相当前后缀 当一个字符不匹配时 可以回退到上一个前后缀相等的位置 再次开始匹配 不用再遍历一次 #include iostreamusing namespace std;const int N 100010, M 1000010;int n, m;int ne[N];char s[M], p[N]; //注意是charint main(){//从1开始 回退时直接回退到ne[j];cin n p 1 m s 1;//i从2开始 因为ne[1]一定为0for (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 ; //匹配时jne[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) //找到子串{couti-n ;j ne[j]; //可能出现两个子串重叠的情况}}return 0;}
