빠른 2 차원 패턴 매칭

Question

2 차원 격자 (평면상의 일반적인 격자)를 고려하십시오. 내 목적을 위해 패턴 또는 배열은 격자 포인트의 일부 연결된 하위 세트에 1과 2 숫자를 지정하는 것입니다. 예를 들어, 다음 쇼 세 가지 별도의 준비는 :

.......1.....1.... 
.222...2.....12... 
.111...2.....2.... 
.222...22...12211. 
.......1....11.1.. 

나는 그것의 모든 숫자가 더 큰의 숫자보다 작은 것을 작은 하나가 회전하거나 반영 할 수있는 경우 작은 패턴이 큰 하나와 일치라고 하나. 이 회전 또는 3 × 3 사각형에 맞게 반영 할 수 없기 때문에

...... 
.1212. 
....2. 
...... 

그것은 가장 왼쪽에 배치 위 일치하지 않습니다 예를 들어,이 패턴을 고려하십시오. 그것은 아래에 맞게 회전되고 반사 될 수 있기 때문에 중간 배치와 일치합니다. 그러나 가장 오른쪽 정렬에 맞도록 회전되거나 반사되기 때문에 가장 오른쪽 배열과 일치하지 않습니다. 숫자는 큰 배열보다 작은 패턴에서 더 큽니다. (어떤 예가 불분명하거나 더 많은 정보가 필요하다면, 주석 영역에서 물어보기 만하면됩니다. 미리 설명해 두십시오 : 패턴을 늘일 수 없으며 그리드를 기준으로 대각선으로 회전 할 수 없습니다 . 즉 번역 할 수 있습니다 각각의 총 네 개의 회전 네 반사가 존재 의미)

나는 다음과 같은 질문에 대해 궁금 :. 작은 패턴이 일치하는 경우 I 빠르게 테스트 할 수있는 방법

1. 을 큰 배열?

2. 작은 패턴이 많이 있다고 가정 해 보겠습니다. 내가 적어도 하나의 중 하나가 합의와 일치하는지 빨리 알기 위해 사전 처리 할 수 ​​있습니까?

가 나는 해결책이 (-뿐만 아니라 1, 2 - 임의의 숫자와 같은 또는 수 연결이 끊어진 모양) 더 일반적인 문제를 해결하는 경우가 멋있다고 생각,하지만 난 정말 단 위의 경우에 관심 . 감사.

Answer 1

2D 컨볼 루션.
(복잡성은 n * Log (n), 요소의 수는 n) 큰 행렬에 적합 할 수 있습니다.

두 행렬이 일치하고 일치하지 않는 동일한 크기로 만듭니다.

각 번호를 seperatly 테스트하십시오. 예 - 컨볼 루션의 결과이고 serchung 매트릭스는 수 k 을 cheking (큰) 0

에 1 개 세트 patteren 매트릭스 설정치 1
에 0 다른 값 < = K를 참조> = K를 설정할 0 공격 및 일반 comlexity는 k는 숫자의 수는 (귀하의 경우 2)는 K N 로그 (N) 것을 의미 각 회전 및 감상 (총 8)

에 대한 일치

확인하고, 더 큰 행렬의 n 개의 요소 수)