kmp 红太狼 2021-06-22 15:37 362阅读 0赞 如果s[i] != p[j+1] 时,令k=ne[j] ,k就是使最长前缀=后缀长度移动的最短距离 由匹配数组ne的含义可知 p[1..k] = p[j-k+1..j] #include <iostream> #include <vector> #include <cstring> #include <algorithm> using namespace std; const int maxn=1e5+10; int n,m; char p[maxn],s[maxn]; //p为模板串，s为模式串 int ne[maxn]; void getnext(){ for(int i=2,j=0;i<=n;i++){ //因为next[i]的定义是非本身的最大后缀等于最大前缀，即必须要小于i，所以next[1]必须等于0，i就只能从2开始循环了。 while(j&&p[i]!=p[j+1]){ //j和i错开一位每次拿j+1的值与i比 j=ne[j];//如果一直匹配失败，就一直返回直到连首字符都不匹配 } if(p[i]==p[j+1]){ j++;//匹配了就向后移一位 } ne[i]=j; } } int main(){ cin>>n>>p+1>>m>>s+1;//下标都从一开始计数 getnext();//求next数组 for(int i=1,j=0;i<=m;i++){ while(j&&s[i]!=p[j+1]){ //匹配的过程基本与求next数组一样 j=ne[j]; } if(s[i]==p[j+1]){ j++; } if(j==n){ cout<<i-j<<" ";//由于本身字符串是从0开始计数的在i-j+1的基础上要减个1 j=ne[j];//接着找下一个匹配的位置 //因为匹配成功后，p[j + 1]相当于是空字符，一定不匹配s[]中的任何字符，所以可以更新一次j。 } } return 0; }
相关 kmp算法和kmp的优化 一、kmp是什么 KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简 以你之姓@/ 2023年07月13日 03:40/ 0 赞/ 3 阅读
相关 KMP （1）next\[0\]= -1 意义：任何串的第一个字符的模式值规定为-1。 （2）next\[j\]= -1 意义：模式串T中下标为j的字符，如果与首字符 相同，且 电玩女神/ 2022年07月26日 06:18/ 0 赞/ 114 阅读
相关 kmp include <iostream> include <cstdio> include <string> include <cstring> 曾经终败给现在/ 2022年06月09日 07:51/ 0 赞/ 155 阅读
相关 KMP模板 1 include <iostream> 2 include <string> 3 using namespace std; 4 / P ╰+攻爆jí腚メ/ 2021年12月20日 23:57/ 0 赞/ 185 阅读
相关 Kmp算法 举例来说，有一个字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一个字符串"ABCDABD"？ ![bg2013050101.jpg][] 迷南。/ 2021年12月17日 11:13/ 0 赞/ 345 阅读
相关 KMP KMP 输出 版本二 include<bits/stdc++.h> using namespace std; const in 今天药忘吃喽~/ 2021年12月04日 07:49/ 0 赞/ 172 阅读
相关 KMP算法 一 KMP算法介绍 1 KMP是一个解决模式串在文本串是否出现过，如果出现过，求算出现的位置的经典算法。 2 Knuth-Morris-Pratt 字符串查找算法，简称 傷城~/ 2021年07月24日 18:29/ 0 赞/ 589 阅读
相关 kmp 如果s[i] != p[j+1] 时,令k=ne[j] ,k就是使最长前缀=后缀长度移动的最短距离 由匹配数组ne的含义可知 p[1..k] = p[j-k+1 红太狼/ 2021年06月22日 15:37/ 0 赞/ 363 阅读
相关 KMP代码 #include <stdio.h> #include <string.h> char a[] = "abababaababacb"; char b[] = ... 朱雀/ 2021年03月28日 15:32/ 0 赞/ 519 阅读
以你之姓@
╰+攻爆jí腚メ
迷南。
今天药忘吃喽~
傷城~
红太狼
朱雀
还没有评论，来说两句吧...