A Fast Exact String Matching Algorithm Based on Nested Classification

(*) Corresponding author

Authors' affiliations

DOI's assignment:
the author of the article can submit here a request for assignment of a DOI number to this resource!
Cost of the service: euros 10,00 (for a DOI)


This paper makes a research on the exact string matching, proposed a nested classification string matching algorithm. This paper based on the KMP algorithm, constructs the multi-level string matching and use the KR algorithm calculates the next function quickly, in order to replace the traditional KMP algorithm which is using the recursive thinking to calculate the next[j] function value in the large number of pattern string under the premise. Through the use of this method we can reduce the number of matches thereby raising the efficiency.
Copyright © 2013 Praise Worthy Prize - All rights reserved.


String Matching; Nested Classification; KMP Algorithm; KR Algorithm

Full Text:



Guo-liang Cheng. Design and Analysis of Parallel Algorithms [M]. Beijing: Higher Education Press, 2009.

Long-Tao He, Bin-Xing Fang, Xiang-Zhan Yu. A Time Optimal Exact String Matching Algorithm [J]. Journal of Software, 2005, 16(5): 676-683.

Wei-min Yan, Wei-ming Wu. Data Structure [M]. Beijing: Tsinghua University Press, 2007.

Rui-xia Li, Hui Zhou, Reng-rong Yan. Research and Realization on Parallel Exact String Matching [J]. Journal of Shijiazhuang University, 2009, 11(6): 58-63.

Yan-kun Li, Wei-na Fu, Shuai Liu, Ming Zhu. KMP String Matching Algorithm in Parallel system [J]. Manufacturing automation, 2011,33(2):189-191.

Jin-xiong Zhang, Zheng-you Liang, De-xia Cai, Xing-liu Wei. Implementing Parallel Algorithm for Approximate String Matching with k-differences based on GPU [J]. Journal of Guangxi University, 2011,36(2): 285-291.

Jin-zhu Hu, Chun-xiu Xiong, Jiang-bo Shu, Wen-tao Cheng. An Improved Character String Pattern Matching Algorithm [j]. Pattern Recognition And Artificial Intelligence, 2010, 23(1): 391-395.

N. Belhaouchet, L. Rahmani, S. Begag, Three-Phase Shunt Active Power Filter with High-Performance Operation, (2008) International Review of Automatic Control (IREACO), 1 (3), pp. 294-302.

Zhiyuan Shi, Yuqiang Sun, Yuwan Gu, Fuquan Ji, Jingfen Du. The Study about Parsing of RGG Grammar. Advanced Materials Research.

K. Abed, K. Nabti, H. Benalla, High-Performance Intelligent Sensorless Control of Induction Machine Based Extended Luenberger and Kalman Filter Observers Using Fuzzy-PI Controller, (2008) International Review of Automatic Control (IREACO), 1 (1), pp. 57-64.

B. N. Kathir, A. R. Sebak, Electromagnetic Wave Scattering by Parallel Dielectric/Metamaterial Coated Elliptic Cylinders, (2008) International Review on Modelling and Simulations (IREMOS). 0 (0), pp. 41-48.


  • There are currently no refbacks.

Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2023 Praise Worthy Prize