Faster two-dimensional pattern matching with rotations期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

Faster two-dimensional pattern matching with rotations

Authors:	Amihood Amir Oren Kapah Dekel Tsur

Affiliation:	1. Department of Computer Science, Bar-Ilan University, 52900 Ramat-Gan, Israel and Georgia Tech;2. Department of Computer Science, Bar-Ilan University, 52900 Ramat-Gan, Israel;3. Department of Computer Science, Ben-Gurion University of the Negev. Be’er Sheva 84105, Israel

Abstract:	The most efficient currently known algorithms for two-dimensional pattern matching with rotations have a worst case time complexity of O(n²m³) $O (n^{2} m^{3})$ , where the size of the text is n×n $n \times n$ and the size of the pattern is m×m $m \times m$ . In this paper we present a new algorithm for the problem whose running time is O(n²m²) $O (n^{2} m^{2})$ .

Keywords:	Design and analysis of algorithms Two-dimensional pattern matching Rotation
本文献已被 ScienceDirect 等数据库收录！