Theoretical Research of KMP Algorithm

HAN Guang-hui; CENG Cheng

Chinese

您当前的位置：

首页 >

文章列表页 >

Theoretical Research of KMP Algorithm

更新时间：2026-09-04

- Theoretical Research of KMP Algorithm
- Vol. 30, Issue 4, Pages: 30-33(2013)
- 作者机构：
  
  1. 1 武汉商业服务学院信息工程系,湖北,武汉,430056
  2. 2 湖北大学机构数学与计算机科学学院,湖北,武汉,430062
  3. 3 武汉大学软件工程国家重点实验室机构,湖北,武汉,430072
- 作者简介：
- 基金信息：
- DOI：
  CLC：
- Published：2013
- 稿件说明：
移动端阅览
韩光辉, 曾诚. KMP算法的理论研究[J]. 微电子学与计算机, 2013, 30(4): 30-33.

HAN Guang-hui, CENG Cheng. Theoretical Research of KMP Algorithm[J]. 2013, 30(4): 30-33.
韩光辉, 曾诚. KMP算法的理论研究[J]. 微电子学与计算机, 2013, 30(4): 30-33. DOI：

HAN Guang-hui, CENG Cheng. Theoretical Research of KMP Algorithm[J]. 2013, 30(4): 30-33. DOI：

摘要

KMP算法是经典的串匹配算法之一.本文首先引入刻划模式串前缀特征的集合及其划分

讨论了其若干性质.然后定义函数与next

利用刻划了的构造

由此得到了的迭代计算方法;证明了next与之间的关系

从而给出了KMP算法原理的形式表述和数学证明.最后

基于的迭代计算方法以及next与之间的关系

给出了算法描述

分析了时间复杂度.

Abstract

KMP algorithm is one of classic string matching algorithms.A set

for 1 <≤m

which characterize a pattern prefix

and its partition are introduced

their some properties are discussed.Then

functions and next are defined

the structure of is described by

a iterative computing method of is proposed

the relationship between functions next and is proved.Thus

mathematical principles of KMP algorithm is strictly established. Finally

the algorithm is described based on the iterative computing method of and the relationship between functions next and

and its complexity is analyzed.

关键词

Keywords

references

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Design of ultra-low power real-time clock circuits

Simulation on the DC characteristics of double heterojunction p-GaN HEMT with AlN/GaN hybrid buffer layer

Microservices anomaly detection based on the correlation of monitoring metrics

Aerial small object detection algorithm based on improved RT-DETR

Implementation and verification of a dual-chain power gating strategy for low power design

Related Author

No data

Related Institution

No data

AI问答

Postal code：100079
Tel：（010）53879206 Email：tmw@bjxintong.com.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09082226号-64 京公网安备11010602201714号
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰