Implementation and Analysis Zhu-Takaoka Algorithm and Knuth-Morris-Pratt Algorithm for Dictionary of Computer Application Based on Android

Handrizal Handrizal(1*), Andri Budiman(2), Desy Rahayu Ardani(3),

(1) AMIK Tunas Bangsa Pematangsiantar
(2) University of Sumatera Utara
(3) University of Sumatera Utara
(*) Corresponding Author


The string matching algorithm is the one of the most important parts in the various processes related to data and text types, which is the word search on computer dictionary. Computers have a basic role in the field of education, especially in teaching and learning activities. So that the classical learning model, that is by using the book as learning resource can be boring. To make it easier for users who searching words, we made an offline dictionary application based on Android by applying Zhu-Takaoka algorithm and Knuth-Morris-Pratt algorithm. The performance of Zhu-Takaoka is doing a search starts from the end of pattern that is tailored to the text, but in Knuth-Morris-Pratt algorithm starts from the beginning of pattern till match which the pattern used is word searched. The result of this research indicates that the Zhu-Takaoka algorithm is faster than the Knuth-Morris-Pratt algorithm which showed the running time of each algorithm.

Full Text:



Charras, C. & Lecroq, T. 2004. Handbook of Exact String-Matching Algorithms. London: King’s College Publications.

Abu-Zaid, Ibrahim M. & Emad Kh. El-Rayyes. 2012. Parallel Search Using KMP Algorithm in Arabic String. Int. J. of Science and Technology. Vol.2 No.7 : pp. 2224-3577.

Wayne,K. & Sedgewick, R. 2014. Algorithms Fourth Edition: Substring Searc.

ZHU, R.F. and TAKAOKA, T. 1987. On Improving the Average Case of The Boyer-

Moore String Matching Algorithm. Journal of Information Processing 10(3) pp.173 177.

Sumit K. Aggarwal, 2005. Analysis of string-searching algorithms on biological sequence databases. Research Communications, Vol. 89, No. 2 pp. 368-374.

Singla, Nimisha & Deepak Garg. 2012. String Matching Algorithms and Their Applicability in various Application, Int. J. of Soft Computing and Engineering. Vol.I pp. 2231-2307.

R.Sadli, 2001. Optimization of sequence queries in database systems, Proceeding PODS '01 Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp. 71-81.

Margaret B, 2011. Android: Changing the Mobile Landscape, IEEE pervasive Computing Vol. 10 No. 1 pp 4-7.



  • There are currently no refbacks.

Jumlah Kunjungan:

View My Stats

Published Papers Indexed/Abstracted By: