kmp

红太狼 2021-06-22 15:37 338阅读 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;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，338人围观）

还没有评论，来说两句吧...

相关阅读

相关 KMP

Kmp详解 [ 朴素匹配算法咱们先来看朴素匹配算法。假设现在文本串S匹配到 i 位置，模式串P匹

一时失言乱红尘/ 2022年08月10日 15:37/ 0 赞/ 97 阅读

相关 KMP

（1）next\[0\]= -1 意义：任何串的第一个字符的模式值规定为-1。（2）next\[j\]= -1 意义：模式串T中下标为j的字符，如果与首字符相同，且

电玩女神/ 2022年07月26日 06:18/ 0 赞/ 94 阅读

相关 KMP算法

1.原始的字符串匹配方法算法基本思想：从主串S的第pos个字符起和模式的第一个字符比较之，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较

「爱情、让人受尽委屈。」/ 2022年06月15日 01:42/ 0 赞/ 162 阅读

相关 kmp

include <iostream> include <cstdio> include <string> include <cstring>

曾经终败给现在/ 2022年06月09日 07:51/ 0 赞/ 132 阅读

相关 KMP模板

1 include <iostream> 2 include <string> 3 using namespace std; 4 / P

╰+攻爆jí腚メ/ 2021年12月20日 23:57/ 0 赞/ 161 阅读

相关 Kmp算法

举例来说，有一个字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一个字符串"ABCDABD"？ ![bg2013050101.jpg][]

迷南。/ 2021年12月17日 11:13/ 0 赞/ 316 阅读

相关 KMP

KMP 输出版本二 include<bits/stdc++.h> using namespace std; const in

今天药忘吃喽~/ 2021年12月04日 07:49/ 0 赞/ 149 阅读

相关 KMP算法

一 KMP算法介绍 1 KMP是一个解决模式串在文本串是否出现过，如果出现过，求算出现的位置的经典算法。 2 Knuth-Morris-Pratt 字符串查找算法，简称

傷城~/ 2021年07月24日 18:29/ 0 赞/ 546 阅读

相关 kmp

如果s[i] != p[j+1] 时,令k=ne[j] ,k就是使最长前缀=后缀长度移动的最短距离由匹配数组ne的含义可知 p[1..k] = p[j-k+1

红太狼/ 2021年06月22日 15:37/ 0 赞/ 339 阅读

相关 KMP代码

#include <stdio.h> #include <string.h> char a[] = "abababaababacb"; char b[] = ...

朱雀/ 2021年03月28日 15:32/ 0 赞/ 469 阅读