• May 27, 2016 News!The submission for Special Issue is officially open now!   [Click]
  • May 03, 2016 News!Vol.6, No.6 has been indexed by EI (Inspec).   [Click]
  • Mar 17, 2017 News!Vol.9, No.2 has been published with online version. 13 peer reviewed articles from 4 specific areas are published in this issue.   [Click]
General Information
Editor-in-chief
Prof. Wael Badawy
Department of Computing and Information Systems Umm Al Qura University, Canada
I'm happy to take on the position of editor in chief of IJCTE. We encourage authors to submit papers concerning any branch of computer theory and engineering.
IJCTE 2010 Vol.2(3): 352-357 ISSN: 1793-8201
DOI: 10.7763/IJCTE.2010.V2.166

Inverted Lists String Matching Algorithms

Chouvalit Khancome and Veera Boonjing

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).

[PDF]

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-2015. International Journal of Computer Theory and Engineering. All rights reserved.
E-mail: ijcte@vip.163.com