Pattern Matching with Swaps for Short Patterns in Linear Time
作者： Domenico Cantone , Simone Faro
DOI: 10.1007/978-3-540-95891-8_25
关键词: 3-dimensional matching 、 General algorithm 、 Pattern matching 、 Combinatorics 、 Disjoint sets 、 Swap (finance) 、 Sigma 、 Mathematics 、 Time complexity
摘要: The Pattern Matching problem with Swaps consists in finding all occurrences of a pattern P text T , when disjoint local swaps the are allowed. In Approximate one seeks, for every location swapped match number necessary to obtain at location. In this paper, we present new approach solving both Swap and linear time, case short patterns. particular, devise $\mathcal{O}(nm)$ general algorithm, named Cross-Sampling show an efficient implementation it, based on bit-parallelism, which achieves $\mathcal{O}(n)$ worst-case time $\mathcal{O}(\sigma)$-space complexity, patterns whose length is comparable word-size target machine.
springer.com
sci-hub.st 参考文章(9)
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
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
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
Ricardo Baeza-Yates, Gaston H. Gonnet, A new approach to text searching Communications of The ACM. ,vol. 35, pp. 74- 82 ,(1992) , 10.1145/135239.135243
Amihood Amir, Yonatan Aumann, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein, Pattern Matching with Swaps Journal of Algorithms. ,vol. 37, pp. 247- 266 ,(2000) , 10.1006/JAGM.2000.1120
Amihood Amir, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein, Efficient special cases of Pattern Matching with Swaps Information Processing Letters. ,vol. 68, pp. 125- 132 ,(1998) , 10.1016/S0020-0190(98)00151-3
Sofsem 2008: Theory and Practice of Computer Science 34th Conference on Current Trends in Theory and Practice of Computer Science. ,(2008) , 10.1007/978-3-540-77566-9
Amihood Amir, Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat, Overlap matching Information and Computation archive. ,vol. 181, pp. 57- ,(2003) , 10.1016/S0890-5401(02)00035-4
A. Amir, Y. Aumann, G.M. Landau, M. Lewenstein, N. Lewenstein, Pattern matching with swaps foundations of computer science. pp. 144- 153 ,(1997) , 10.1109/SFCS.1997.646103