Hızlı iki boyutlu desen eşlemesi

Question

İki boyutlu bir ızgarayı (düzlemdeki genel kafes) düşünün. Benim amaçlarım için, paterni veya veya 10 düzenlemesi, ızgara noktalarının bazı bağlı alt kümelerine 1 ve 2 numaralarının atanmasıdır. Örneğin, aşağıdaki gösterileri üç ayrı düzenlemeler:

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

Ben onun bütün numaraları daha büyük sayılar daha küçük olduğu küçük bir döndürülmüş ya da yansıtılabilir eğer küçük bir örnek büyük eşleştiğini söylemek bir. o döndürülmüş veya 3x3 meydanda sığacak şekilde yansıtılması olamaz çünkü

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

Bu en soldaki düzenleme yukarıda eslesmez: Örneğin, bu desen düşünün. Orta düzenlemeyle eşleşir çünkü dönebilir ve altına sığacak şekilde yansıtılabilir. Bununla birlikte, en sağdaki düzenlemeyle eşleşmez, çünkü en sağdaki düzenlemeye uyması için döndürülür veya yansıtılır, rakamlar küçük düzende büyük düzenlemeden daha büyüktür. (Örneklerimden herhangi biri belirsizse veya daha fazla bilgiye ihtiyaç duyarsanız, yalnızca yorumlar bölümünde sorun. Önceden bazı açıklamalar: desen gerilmeyebilir ve bu nedenle döndürülemez. . Yani tercüme edilebilir, her biri toplam dört rotasyonlar ve dört yansımaları vardır demektir)

aşağıdaki soruları merak ediyorum. küçük bir desen, bir eşleşirse çabuk nasıl test edebilir

1. büyük düzenleme?

2. Çok sayıda küçük desenim olduğunu varsayalım. Bunlardan bir tanesinin en az bir bir düzenlemeyle eşleşip eşleşmediğini hızlı bir şekilde anlatabilir miyim?

Bir çözüm (- sadece 1 ve 2 - keyfi numaraları gibi ya izin bağlantısız şekiller) daha genel bir sorunu çözer eğer süper olurdu herhalde, ama gerçekten sadece Yukarıdaki durumda umurumda . Teşekkürler.

Answer 1

2B evrişim.
(karmaşıklık n * Log (n) öğelerin sayısı bakımından n) ve daha büyük matrisler için iyi olabilir.

Her ikisi de eşleşen ve aynı boyutta eşleşmeyen matrisler yapın.

Her bir sayı için ayrı ayrı test edin. Örnek - konvolüsyon sonucu olduğu durumda serchung matriste sayısı k cheking (büyük) 0

1 diğer sette patteren matris ayar değerleri 1
0 diğer değerlere < = k numaraları> = k ayarlamak 0 vurmak ve genel comlexity k numaralarının sayısı (sizin durumunuzda 2'de) 'dir k n log (n) olduğu anlamına her rotasyon ve yansıma (8 toplam)

için maç

kontrol edilir ve n büyük matris elemanlarının sayısı)