文档章节

KMP算法的理解与实现

memristor
 memristor
发布于 2014/04/14 12:32
字数 398
阅读 45
收藏 0

KMP算法用于字符串匹配

关于next数组的解释参见:http://my.oschina.net/shaorongjie/blog/163967

KMP算法比较详尽的一个解释见 http://kenby.iteye.com/blog/1025599】

http://www.cnblogs.com/waytofall/archive/2012/10/27/2742163.html

KMP算法详解——适合初学KMP算法的朋友http://billhoo.blog.51cto.com/2337751/411486

KMP算法深度解析http://blog.csdn.net/liuaigui/article/details/4409505

模式匹配的KMP算法详解




改写java版本如下:

import java.util.Arrays;

public class KMPtest {
	public static int[] getNextArray(String s) {
		char[] target = s.toCharArray();
		int size = target.length;
		int[] next = new int[size + 1];
		next[0] = 0;
		next[1] = 0;
		int k = 0;// /* 第i次迭代开始之前,k表示next[i-1]的值 */
		for (int i = 2; i < size + 1; i++) {
			for (; k != 0 && target[k] != target[i - 1]; k = next[k]) {
			}
			if (target[k] == target[i - 1]) {
				k++;
			}
			next[i] = k;
		}
		return next;
	}

	public static void kmpmatch(String text, String pattern) {
		int m, n, s, q;
		int[] next = getNextArray(pattern);
		char[] textarray = text.toCharArray();
		char[] patternarray = pattern.toCharArray();
		m = patternarray.length;
		n = textarray.length;
		q = s = 0; // q表示上一次迭代匹配了多少个字符, s表示这次迭代从text的哪个字符开始比较
		while (s < n) {
			for (q = next[q]; q < m && patternarray[q] == textarray[s]; q++, s++) {
			}
			if (q == 0) {
				s++;
			} else if (q == m) {
				System.out.println("matched success at " + (s - m));
			}
		}
	}

	public static void main(String[] args) {
//		int[] next = getNextArray("abababca");
//		System.out.println(Arrays.toString(next));
		kmpmatch("bdcaccacaercacdcaca", "caca");
	}

}

运行结果:

matched success at 5

matched success at 15



© 著作权归作者所有

memristor
粉丝 45
博文 203
码字总数 176319
作品 0
长沙
程序员
私信 提问
数据结构与算法JavaScript (五) 串(经典KMP算法)

KMP算法和BM算法 KMP是前缀匹配和BM后缀匹配的经典算法,看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同 前缀匹配是指:模式串和母串的比较从左到右,模式串的移动也是从 左到右...

文艺小青年
2017/06/01
0
0
JavaScript 字符串匹配算法

原文链接 前言 字符串匹配算法,在日常开发中也常被频繁用到。当然,我们可以用正则匹配来完成字符串匹配,但是,学习和理解相关的字符串匹配算法,对于我们技术成长还是有很多好处的。 定义...

Checkson
07/25
0
0
KMP 字符串匹配经典算法深度解析

摘要:KMP算法是字符串匹配的经典算法,由于其O(m+n)的时间复杂度,至今仍被广泛应用。大道至简,KMP算法非常简洁,然而,其内部却蕴含着玄妙的理论,以至许多人知其然而不知其所以然。本文旨...

红薯
2011/08/10
2.5K
0
串的应用与kmp算法讲解--学习笔记

串的应用与kmp算法讲解 1. 写作目的 平时学习总结的学习笔记,方便自己理解加深印象。同时希望可以帮到正在学习这方面知识的同学,可以相互学习。新手上路请多关照,如果问题还请不吝赐教。 ...

huangzhuyun
06/06
0
0
KMP算法的next[]数组通俗解释

前言 本文是对KMP核心部分NEXT数组的构建方法说明,KMP整体分析的文章可以参考下面的链接。 http://my.oschina.net/u/572632/blog/277548 概述 我们在一个母字符串中查找一个子字符串有很多方...

面码
2014/06/18
3.8K
1

没有更多内容

加载失败,请刷新页面

加载更多

CRM、DMP、CDP都是什么?有什么区别?

Markter对CRM系统(Customer Relationship Management System,客户关系管理系统),营销自动化等概念都已经比较熟悉,也许DMP(Data Management Platform,数据管理平台)也多多少少有些了解。...

怡海软件-CRM
18分钟前
4
0
中台是什么,到底要解决什么问题?

故事的开始 这个最早由阿里在2015年提出的“大中台,小前台”战略中延伸出来的概念,最近在国内大热。阿里、腾讯、百度、京东、美团、滴滴等一众互联网巨头,从去年到今年,接连开始组织架构...

喵二狸
29分钟前
3
0
Linux Centos 7 - MySQL 5.7离线安装

内部网络通过离线包的方式进行安装。 一、下载 下载地址:https://dev.mysql.com/downloads/mysql/ 进入页面后,点击右侧链接。 下载对应版本。 通过xftp6等工具上传到服务器上。 二、安装和...

华山猛男
29分钟前
3
0
EventBus 3 全解

EventBus 3 全解 [TOC] 使用 一个基于观察者模式的事件发布/订阅框架. 用于模块间通信和解耦, 使用方便,性能高. 基本使用 1. gradle导入依赖库 implementation 'org.greenrobot:eventbus:3....

马湖村第九后羿
32分钟前
4
0
HTTP 协议

什么是HTTP协议? HTTP是hypertext transport protocol的缩写,即超文本传输协议。 是用于万维网服务器与本地浏览器之间传输超文本的传送协议。可以使浏览器更加高效,使网络传输减少。能够保...

彩色泡泡糖
42分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部