DocumentCode
3509516
Title
Yet another efficient algorithm for the Swap Matching problem
Author
Ahmed, Pritom ; Islam, A. S M Sohidull ; Rahman, M. Sohel
Author_Institution
Dept. of Comput. Sci., BUET, Dhaka, Bangladesh
fYear
2012
fDate
18-19 May 2012
Firstpage
336
Lastpage
341
Abstract
In this paper, we revisit the much studied problem of Pattern matching with Swaps (Swap Matching problem, for short). We study the graph theoretic model proposed by [8] and using the model, devise an efficient algorithm to solve the swap matching problem. The resulting algorithm is an adaptation of the classic shift-and algorithm. For patterns having length similar to the word-size of the target machine, the algorithm runs in O(n) time, where n and m are the length of the text and the pattern respectively.
Keywords
graph theory; pattern matching; classic shift-and algorithm; graph theoretic model; pattern matching; swap matching problem; target machine word-size; Algorithm design and analysis; Arrays; Computer science; Conferences; Heuristic algorithms; Informatics; Pattern matching;
fLanguage
English
Publisher
ieee
Conference_Titel
Informatics, Electronics & Vision (ICIEV), 2012 International Conference on
Conference_Location
Dhaka
Print_ISBN
978-1-4673-1153-3
Type
conf
DOI
10.1109/ICIEV.2012.6317431
Filename
6317431
Link To Document