Improved KMP algorithm

Journal of East China Normal University(Natural Sc ›› 2009, Vol. 2009 ›› Issue (4): 92-97.

• Article • Previous Articles Next Articles

Improved KMP algorithm

YU Song,ZHENG Jun,HU Wenxin

Computer Center, East China Normal University ，Shanghai200062, China

Received:2008-10-05 Revised:2009-01-23 Online:2009-07-25 Published:2009-07-25
Contact: ZHENG Jun

Abstract

Abstract: This paper established an improved KMPalgorithm for pattern matching in string. Tests proved that the algorithm has less comparison times and higher efficiency under the circumstances that the pattern first appears in the bottom half of a text string.

Key words: pattern, string, time complexity, text , match, pattern, string, time complexity, text

CLC Number:

TP391.4

YU Song;ZHENG Jun;HU Wenxin. Improved KMP algorithm[J]. Journal of East China Normal University(Natural Sc, 2009, 2009(4): 92-97.

[1]	GAO Qin-qin， ZHU Jian-rong， DUAN Yi-hong， SUN Ming-hua. Impacts of the symmetrical and unsymmetrical typhoons on the storm surge simulation in the East China and the South China Seas [J]. Journal of East China Normal University(Natural Sc, 20120, 2012(6): 57-72.
[2]	Rui FU, Jianyu LI, Jiahui WANG, Kun YUE, Kuang HU. Joint extraction of entities and relations for domain knowledge graph [J]. Journal of East China Normal University(Natural Science), 2021, 2021(5): 24-36.
[3]	Yaqin HU, Ming TANG. The impact of coupling patterns on transport in multilayer networks [J]. Journal of East China Normal University(Natural Science), 2021, 2021(3): 105-113.
[4]	Yanchun LIANG, Ailian FANG. Chinese text relation extraction based on a multi-channel convolutional neural network [J]. Journal of East China Normal University(Natural Science), 2021, 2021(3): 96-104.
[5]	CHEN Liangjian, XU Jianqiu. Online map matching algorithm based on the gated recurrent unit model [J]. Journal of East China Normal University(Natural Science), 2020, 2020(6): 63-71.
[6]	HAN Chengcheng, LI Lei, LIU Tingting, GAO Ming. Approaches for semantic textual similarity [J]. Journal of East China Normal University(Natural Science), 2020, 2020(5): 95-112.
[7]	WU Xue, HUANG Li, JIN Cheng, QIAN Shenhua, YANG Yongchuan. Species composition and distribution pattern of weed communities in Chongqing metropolis [J]. Journal of East China Normal University(Natural Science), 2020, 2020(2): 98-109.
[8]	YANG Qingsong, LIU Heming, ZHU Tongtong, ZHANG Shouhe, WANG Xihua. Interspecies associations and species-habitat associations in the evergreen broad-leaved forest of Tiantong National Forest Park, Zhejiang [J]. Journal of East China Normal University(Natural Science), 2020, 2020(2): 110-119.
[9]	WANG Yan, YANG Jifeng. Study on the covariant chiral effective field theory of vector meson [J]. Journal of East China Normal University(Natural Science), 2020, 2020(1): 67-75.
[10]	WANG Guo-liang, CHEN Meng-nan, CHEN Lei. An end-to-end Chinese speech synthesis scheme based on Tacotron 2 [J]. Journal of East China Normal University(Natural Sc, 2019, 2019(4): 111-119.
[11]	YU Ruo-nan, HUANG Ding-jiang, DONG Qi-wen. Survey on scene text detection based on deep learning [J]. Journal of East China Normal University(Natural Sc, 2018, 2018(5): 1-16.
[12]	LI Na, JIN Gang-zeng, ZHOU Xiao-xu, ZHENG Jian-bing, GAO Ming. A survey of entity matching algorithms in heterogeneous networks [J]. Journal of East China Normal University(Natural Sc, 2018, 2018(5): 41-55.
[13]	XU Yang, WANG Zhi-jie, QIAN Shi-you. Distributed spatio-textual analytics based on the Spark platform [J]. Journal of East China Normal University(Natural Sc, 2018, 2018(5): 120-134,153.
[14]	ZHANG Heng, CHEN Liang-yu. Optimization of the Levenshtein algorithm and its application in repeatability judgment for test bank [J]. Journal of East China Normal University(Natural Sc, 2018, 2018(5): 154-163.
[15]	ZHANG Dao-xiang, SUN Guang-xun, HU Wei, KAI Ge. Spatial Turing pattern of a predator-prey system with nonlinear harvesting effect [J]. Journal of East China Normal University(Natural Sc, 2018, 2018(4): 9-22,31.

Improved KMP algorithm

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments