Abstract—This research article presents two algorithms of string pattern matching. These algorithms employ a new data structure called inverted lists structure which is inherited from the inverted index to accommodate a string pattern to be searched. The first solution scans the given text in a single pass for all occurrences of string pattern. The second solution, which improves the first one, takes the comparison times equal to the length of pattern plus the numbers of comparison that lead to be mismatched. For experimental results, these algorithms are efficient in the case of small alphabet sizes.
Index Terms—string pattern matching, inverted lists (IVL), inverted index, string algorithm.
Chouvalit Khancome is a PhD student in Computer Science at King Mongkut’s Institute of Technology Ladkrabang, Thailand. He is a teacher in Department of Computer Science, Rajanakarindra Rajabhat University, Thailand (e-mail: chouvalit@ hotmail.com).
Veera Boojing is An Associate Professor in Computer Science, Department of Mathematics and Computer Science at King Mongkut’s Institute of Technology Ladkrabang, Thailand. Also, he is working in National Centre of Excellence in Mathematics, PERDO, Bangkok, Thailand 10400, (e-mail: kbveera@kmitl.ac.th).
Cite: Chouvalit Khancome and Veera Boonjing, "Inverted Lists String Matching Algorithms," International Journal of Computer Theory and Engineering vol. 2, no. 3, pp. 352-357, 2010.
Copyright © 2008-2024. International Association of Computer Science and Information Technology. All rights reserved.
