Title :
Fastest approach to exact pattern matching
Author :
Hussain, Iftikhar ; Ali, Imran ; Zubair, Muhammad ; Bibi, Nazarat
Author_Institution :
Dept. of Comput. & Technol., Iqra Univ., Islamabad, Pakistan
Abstract :
This research, presents an improved version of Bidirectional (BD) [20] algorithm to solve the problem of exact pattern matching. Fastest-Bidirectional (FBD) exact pattern matching algorithm introduced a new idea of scanning partial text window (PTW) as well with the pattern by taking Berry-Ravindran (BR) consecutive characters to take decision of moving pattern to the right of PTW. FBD algorithm compares the characters of pattern to selected text window from both sides simultaneously as BD. The time complexity of preprocessing phase of FBD algorithm is O(m+ |Σ|) and searching phase takes O(mn/2).
Keywords :
computational complexity; string matching; text analysis; Berry-Ravindran consecutive character; exact pattern matching; fastest bidirectional algorithm; moving pattern; partial text window; preprocessing phase complexity; text window; time complexity; Algorithm design and analysis; Complexity theory; Computer science; Force; Indexes; Pattern matching; Software algorithms; Berry Ravindran; Fastest-Bidirectional; Scanning text window; exact pattern matching;
Conference_Titel :
Information and Emerging Technologies (ICIET), 2010 International Conference on
Conference_Location :
Karachi
Print_ISBN :
978-1-4244-8001-2
DOI :
10.1109/ICIET.2010.5625685
