Time Complexity of Knuth Morris Algorithm and Rejang Algorithm in Rejang-Indonesian Translator

Abstract

Among the pattern-matching algorithms is the Knuth-Morris algorithm. In order to minimize the number of comparisons required and, in the worst scenario, achieve an ideal O(n+m) running time, the Knuth-Morris search algorithm skips unneeded comparisons. Every character in the text and every character in the pattern must be checked at least once by the pattern-matching algorithm. The Knuth-Morris algorithm's primary goal is to preprocess the pattern string P in order to determine the failure function f, which displays P's precise shift, so that earlier comparisons can be reused. In order to extract the fundamental word of the attached sentence, words containing affixes are separated using the Rejang stemming method. The purpose of this research is to determine the time complexity of the Rejang method and the Knuth-Morris algorithm based on affix groups. The Rapid Application Development (RAD) approach, which entails planning, designing, building, and implementing, is used during the research stages. The research results have produced efficient and effective Knuth Morris algorithm and Rejang algorithm, where efficiency is indicated by the algorithm time complexity of O (log n), and effectiveness is indicated by the accuracy results of 99% against testing 6000 affixed words.

Keywords

• knuth morris algorithm, rejang algorithm, time complexity