Thuật toán đếm số lần xuất hiện của ma trận bên trong một lớn hơn

Question

Tôi đang gặp phải sự cố ngay bây giờ, tôi cần đếm số lần ma trận MxM nhất định xuất hiện bên trong một ma trận NxN (cái này phải lớn hơn số đầu tiên). Bất kỳ gợi ý nào về cách thực hiện điều này? Tôi sẽ thực hiện nó trong C và không có tùy chọn để thay đổi nó.

Revision 1

Hi tất cả mọi người, tôi thực sự muốn nói lời cảm ơn đến tất cả các câu trả lời và ý kiến ​​về vấn đề này. Tôi nên nói với bạn rằng sau nhiều giờ làm việc vất vả, chúng tôi đã đi đến một giải pháp không hoàn toàn giống như cách tiếp cận Boyer-Moore, mà đúng hơn là một thuật toán của riêng tôi. Tôi đang lên kế hoạch xuất bản nó một lần được kiểm tra và hoàn thành. Các giải pháp hiện đang được điều chỉnh để được paralelized để tối ưu hóa tốc độ bằng cách sử dụng cụm trường đại học với MPI C Library.

Answer 1

Hm, có vẻ giống như phiên bản chuỗi 2 chiều khớp. Tôi tự hỏi nếu có một phiên bản 2D của Boyer-Moore?

A Boyer-Moore Approach for Two-Dimensional Matching

Ah, rõ ràng là có. :-)

Answer 2

Một cách tiếp cận ngay lập tức lóe lên trong óc:

Hãy đối xử với ma trận lớn như là một chuỗi tuyến tính của N * N "ký tự" và ma trận nhỏ như một biểu thức chính quy tuyến tính của thời gian (M + 1) * M có "ký tự chữ" ở vị trí M đầu tiên của mỗi "hàng" và tương đương với .{N-M} ở vị trí còn lại của mỗi hàng. Biên dịch cụm từ thông dụng thành DFA và chạy nó.

Thời gian tìm tất cả các kết quả phù hợp là O (N * N). Tôi nghi ngờ có những thuật toán fancier mà sẽ làm việc (thích ứng của fancier 1-d thuật toán tìm kiếm chuỗi con) nhưng điều này không phải là quá xấu.

Answer 3

Gần đây, các thuật toán nhanh đã được phát triển để xây dựng cây hậu tố 2D. Đây có thể được sử dụng để tìm thấy bất kỳ submatrix vuông trong một ma trận lớn hơn trong thời gian không phụ thuộc vào kích thước của ma trận lớn hơn:

• http://www.springerlink.com/content/96511486841752h4/
• http://www.springerlink.com/content/e65lt4r77773l29g/

Bạn có thể cần phải là một thuê bao để xem những giấy tờ đó.

Tôi cũng tìm thấy một cách tự do có sẵn này, trong đó mô tả một thuật toán xây dựng ngẫu nhiên đó là dự kiến ​​ tuyến tính thời gian:

• http://www.cs.nyu.edu/cs/faculty/cole/papers/CH00.ps

Tôi hy vọng rằng việc xây dựng một cây hậu tố 2D và tìm kiếm với nó sẽ nhanh hơn nếu bạn cần phải tìm kiếm nhiều submatric khác nhau trong một ma trận đơn, nhưng nó có thể chậm hơn 2D Boyer-Moore nếu bạn sẽ tìm kiếm bên trong một ma trận khác nhau mỗi lần.