CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Parallelization of KMP String Matching Algorithm on Different SIMD Architectures: Multi-Core and GPGPU’s

by Akhtar Rasool, Nilay Khare
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 49 - Number 11
Year of Publication: 2012
Authors: Akhtar Rasool, Nilay Khare
10.5120/7672-0963

Akhtar Rasool, Nilay Khare . Parallelization of KMP String Matching Algorithm on Different SIMD Architectures: Multi-Core and GPGPU’s. International Journal of Computer Applications. 49, 11 ( July 2012), 26-28. DOI=10.5120/7672-0963

@article{ 10.5120/7672-0963,
author = { Akhtar Rasool, Nilay Khare },
title = { Parallelization of KMP String Matching Algorithm on Different SIMD Architectures: Multi-Core and GPGPU’s },
journal = { International Journal of Computer Applications },
issue_date = { July 2012 },
volume = { 49 },
number = { 11 },
month = { July },
year = { 2012 },
issn = { 0975-8887 },
pages = { 26-28 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume49/number11/7672-0963/ },
doi = { 10.5120/7672-0963 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:46:01.656437+05:30
%A Akhtar Rasool
%A Nilay Khare
%T Parallelization of KMP String Matching Algorithm on Different SIMD Architectures: Multi-Core and GPGPU’s
%J International Journal of Computer Applications
%@ 0975-8887
%V 49
%N 11
%P 26-28
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

String matching is a classical problem in computer science. After the study of the Naïve string search, Brute Force and the KMP algorithm, several advantages and disadvantages of the algorithms have been analyzed. Considering KMP in particular concept of parallelization has been introduced to improve the performance of the KMP algorithm. The algorithm is designed to work on SIMD parallel architecture where text is divided for parallel processing and special searching at division point is required for consistent and complete searching. This algorithm reduces the number of comparisons and parallelization improves the time efficiency. This algorithm achieves a better result as compared to the multithreaded version of the algorithm where again by text dividing, the parallelization is achieved.

References
  1. Published IEEE papers related to confined topics of KMP and other string matching algorithms, references as , Knuth DE,Morris JH,Pratt V R. Fast pattern in strings[J]. SIAM Journal on Computing,1977,6(2):323-350.
  2. Tang Va-ling. KMP algorithm in the calculation of next array. Computer Technology and Development [J] . 2009,19 (6) :98-101.
  3. Published IEEE papers related to confined topics of KMP and other string matching algorithms, references as, Knuth DE,Morris JH,Pratt V R. Fast pattern in strings[J]. SIAM Journal on Computing, 1977,6(2):323-350.
  4. WANG Jian-guo, ZHENG Jia-Heng. "BM string matching algorithm for an improved algorithm". Computer Engineering and Science, 2007, 29 (5): 94-95.
  5. ZHANG Hong-mei, Fan Ming-yu. "Pattern matching BM Algorithm" [J]. Computer Applications . 2009,26 (9): 3249- 3252.
  6. YUAN Jing-bo, ZHENG Ji-sen, DING Shun-Ii. "A kind of BM pattern matching algorithm" [J] Computer Engineering and Applications, 2009,45 (17) :105-107.
  7. Wu Xi-hong, Ling Jie. "BM pattern matching algorithm" in Computer Engineering and Design, 2007,28 (I): 29-30.
Index Terms

Computer Science
Information Sciences

Keywords

KMP SIMD Parallel KMP

Powered by PhDFocusTM