Parallel pattern matching with swaps on a linear array
作者： Fouad B. Chedid
DOI: 10.1007/978-3-642-13119-6_4
关键词:
摘要: The Pattern Matching with Swaps problem is a variation of the classical pattern matching in which match allowed to include disjoint local swaps In 2009, Cantone and Faro devised new dynamic programming algorithm for this that runs time O(nm), where n length text m paper, first, we present an improved formulation approach Then, optimal parallelization our algorithm, based on linear array model, O(m2) using $\lceil \frac {m-1}\rceil$ processors.
springer.com
sci-hub.st 参考文章(19)
Costas S. Iliopoulos, M. Sohel Rahman, A new model to solve the swap matching problem and efficient algorithms for short patterns conference on current trends in theory and practice of informatics. pp. 316- 327 ,(2008) , 10.1007/978-3-540-77566-9_27
Combinatorial Algorithms on Words Springer-Verlag New York, Inc.. ,(1985) , 10.1007/978-3-642-82456-2
M. S. Paterson, M. J. Fischer, STRING-MATCHING AND OTHER PRODUCTS Massachusetts Institute of Technology. ,(1974)
S. Muthukrishnan, New results and open problems related to non-standard stringology combinatorial pattern matching. pp. 298- 317 ,(1995) , 10.1007/3-540-60044-2_50
U Vishkin, Gad M Landau, Efficient Parallel and Serial Approximate String Matching ,(2011)
Domenico Cantone, Simone Faro, Pattern Matching with Swaps for Short Patterns in Linear Time conference on current trends in theory and practice of informatics. pp. 255- 266 ,(2009) , 10.1007/978-3-540-95891-8_25
Zvi Galil, Open Problems in Stringology Springer, Berlin, Heidelberg. pp. 1- 8 ,(1985) , 10.1007/978-3-642-82456-2_1
SOFSEM 2009: Theory and Practice of Computer Science Lecture Notes in Computer Science. ,vol. 5404, pp. 1- 670 ,(2009) , 10.1007/978-3-540-95891-8
U Vishkin, G M Landau, Efficient String Matching With K Mismatches ,(2018)
Amihood Amir, Moshe Lewenstein, Ely Porat, Approximate swapped matching Information Processing Letters. ,vol. 83, pp. 33- 39 ,(2002) , 10.1016/S0020-0190(01)00302-7