1、BNDM算法与BDM相似,它维护一个集合,即位向量D=Dm....D1,用这个位向量的位记录u在P的反转串中的所有出现位置(因为D的构造是从Dm到D1,不是从D1到Dm,所以用反转),用这种并行算法代替后缀自动机来识别模式串的子串。如果子串Pj....P(j+|u|+1)等于u,那么D的第m-j+1位是1,表示p的位置j是一个活动状态。
2、当读入一个新的文本字符σ时,要从D更新到D',D'的活动状态j对应于σu在模式串的起始位置:
1)u出现在模式串的位置j+1,D的j+1位活动
2)σ在模式串的j位出现.
3、BNDM方法预先计算表B,B的每个元素代表了每个字符的位向量。
D的更新方式分以下2步:
1)D1'<-D&B[σ]
2)D'<-D1<<1
以上方法先检查匹配,再移位,因为D预置为每位全是1
3、代码
4、例子
模式串P=ATATA,文本串=AGATACGATATATAC
1)P的反转串=ATATA
2)表B
A :10101(如右边的A在右边起第1位,所以在最左边的第1位)
T :01010
* :00000
D = 11111
3)在窗口中从后向前读入文本中的字符
[AGATA]CGATATATAC:
(last=5,j>0)
11111&10101->10101
(Dm=1=>last=4,j>0)
01010&01010->01010
10100&10101->10100
(Dm=1=>last=2,j>0)
01000&00000->00000
4)D全0=>pos=pos+last=pos+2,D全置1
AG[ATACG]ATATATAC:
(last=5,j>0)
11111&00000->00000
5)D全0=>pos=pos+last=pos+5,D全置1
AGATACG[ATATA]TAC:
(last=5,j>0)
11111&10101->10101
(Dm=1=>last=4,j>0)
01010&01010->01010
10100&10101->10100
(Dm=1=>last=2,j>0)
01000&01010->01000
10000&10101->10000
(Dm=1,j=0=>匹配成功)
6)D全0=>pos=pos+last=pos+2,D全置1
AGATACGAT[ATATA]C:
(last=5,j>0)
11111&10101->10101
(last=4,j>0)
01010&01010->01010
10100&10101->10100
(last=2,j>0)
010000&01010->01000
10000&10101->10000
(Dm=1,j=0=>匹配成功)
7)pos>n-m,结束
分享到:
相关推荐
字符串匹配算法之BNDM原版(英文原版)
串匹配算法 1 第一章 引言 2 第一节 2 第二节 2 第二章 精确串匹配算法 3 引论 精确串匹配算法的分类 3 第一节 单模式串匹配算法 3 第二节 多模式串匹配算法 20 第三章 近似串匹配算法 27 第一节 引言 27 第二节 ...
Backward Nondeterministic Dawg Matching algorithm
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
本文档是课题研究的研究报告内含调研以及源码设计以及结果分析
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
多线程应用程序设计.pdf
蚁群算法路径规划matlab
IEC 60695-11-3:2012.pdf
触屏版自适应手机wap软件网站模板 触屏版自适应手机wap软件网站模板
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
触屏版自适应手机wap软件网站模板 触屏版自适应手机wap软件网站模板
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
python实现的基于蒙特卡洛树搜索的AI黑白棋源码带详细注释.zip python实现的基于蒙特卡洛树搜索的AI黑白棋源码带详细注释.zip python实现的基于蒙特卡洛树搜索的AI黑白棋源码带详细注释.zip python实现的基于蒙特卡洛树搜索的AI黑白棋源码带详细注释.zip python实现的基于蒙特卡洛树搜索的AI黑白棋源码带详细注释.zip python实现的基于蒙特卡洛树搜索的AI黑白棋源码带详细注释.zip python实现的基于蒙特卡洛树搜索的AI黑白棋源码带详细注释.zip
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
孪生神经网络-python源码.zip
触屏版自适应手机wap软件网站模板 触屏版自适应手机wap软件网站模板
触屏版自适应手机wap软件网站模板 触屏版自适应手机wap软件网站模板