[HackerRank]棋盤搜尋(The Grid Search)

題目描述

給一個由0~9數字組成的二維陣列，接著要使用二維的樣本嘗試在這個陣列中搜尋符合樣本的數字。

舉例來說，下面是一個二維陣列的圖形G：

假設我們要尋找的二維陣列樣本P是：

如果我們掃描原本的圖形G，我們可以發現從第二列到第四列的第三行到第八行，符合樣本P。因此可以說樣本P在圖形G裡面。

原題網址

輸入格式

輸出格式

如果樣本P存在於圖形G，輸出「YES」，否則輸出「NO」。

範例輸入

範例輸出

額外解釋

第一組資料可以在圖形G內找到樣本P：

第二組資料無法在圖形G內找到樣本P。

解題概念

在這題目中，由於二維陣列資料量很大(長度可達1000x1000)，因此必須使用一個快速的方法來解決這個問題。

要如何用比較快的方法來找出樣本P是否在圖形G裡面呢？首先我們可以先找出樣本P的第一列在圖形G裡的位置，把圖形G的一列作為一段文字，樣本P的第一列當作是要在這段文字內尋找的字串。我們可以透過字串搜尋，來找出樣本P的第一列在圖形G的某列出現的所有位置。接著再比較樣本P的第二列至最後一列，是否都符合圖形G對應的位置。

由於可能要進行很多次的字串搜尋，在此筆者使用了Boyer-Moore-MagicLen這個字串演算法來提升搜尋速度。有關Boyer-Moore-MagicLen的說明可以參考這篇：

參考答案

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Solution {

    public static Integer[] magicQuickSearch(final char[] source, final char[] pattern, final int offset, final int limit) {
        final int sourceLength = source.length;
        final int patternLength = pattern.length;

        if (patternLength == 0 || offset < 0 || sourceLength - offset < patternLength) {
            return null;
        }

        final int sourceLength_dec = sourceLength - 1;
        final int patternLength_dec = patternLength - 1;

        final ArrayList<Integer> result = new ArrayList<>();

        final int[] badCharShiftMap = new int[65536];
        Arrays.fill(badCharShiftMap, patternLength);
        for (int i = 0; i < patternLength_dec; ++i) {
            final int index = (int) pattern[i];
            badCharShiftMap[index] = patternLength_dec - i;
        }
        final char specialChar = pattern[patternLength_dec];
        final int specialShift = badCharShiftMap[(int) specialChar];
        badCharShiftMap[(int) specialChar] = 0;

        int sourcePointer = offset + patternLength_dec;
        int patternPointer;

        while (sourcePointer < sourceLength) {
            patternPointer = patternLength_dec;

            while (patternPointer >= 0) {
                if (source[sourcePointer] != pattern[patternPointer]) {
                    break;
                }
                --sourcePointer;
                --patternPointer;
            }

            final int starePointer = sourcePointer;
            final int goodSuffixLength_inc = patternLength - patternPointer;
            sourcePointer += goodSuffixLength_inc;

            if (patternPointer < 0) {
                result.add(starePointer + 1);
                if (sourcePointer > sourceLength_dec || limit > 0 && result.size() == limit) {
                    break;
                } else {
                    final int shift = badCharShiftMap[(int) source[sourcePointer]];
                    sourcePointer += shift;
                    continue;
                }
            }

            final int shift1 = (sourcePointer <= sourceLength_dec) ? badCharShiftMap[(int) source[sourcePointer]] : 0;
            if (shift1 >= patternLength_dec) {
                sourcePointer += shift1;
            } else {
                final int shift2 = ((source[starePointer] == specialChar) ? specialShift : badCharShiftMap[(int) source[starePointer]]) - goodSuffixLength_inc;
                sourcePointer += (shift1 >= shift2) ? shift1 : shift2;
            }
        }

        return result.toArray(new Integer[result.size()]);
    }

    public static void main(final String[] args) throws Exception {
        final Scanner sc = new Scanner(System.in);
        int testCase = Integer.parseInt(sc.nextLine());
        testCase:
        while (testCase-- > 0) {
            final String[] RC = sc.nextLine().split(" ");
            final int R = Integer.parseInt(RC[0]);
            final int C = Integer.parseInt(RC[1]);

            final char[][] g = new char[R][];
            for (int i = 0; i < R; ++i) {
                final char[] cc = sc.nextLine().toCharArray();
                g[i] = cc;
            }

            final String[] rc = sc.nextLine().split(" ");
            final int r = Integer.parseInt(rc[0]);
            final int c = Integer.parseInt(rc[1]);
            final char[][] p = new char[r][c];
            for (int i = 0; i < r; ++i) {
                final char[] cc = sc.nextLine().toCharArray();
                p[i] = cc;
            }

            final int Rr = R - r;

            // Search from top-left
            for (int top = 0; top <= Rr; ++top) {
                final Integer[] availableTopLeft = magicQuickSearch(g[top], p[0], 0, 0);

                if (availableTopLeft.length > 0) {
                    search:
                    for (final int left : availableTopLeft) {
                        for (int i = 1; i < r; ++i) {
                            for (int j = 0; j < c; ++j) {
                                if (g[top + i][left + j] != p[i][j]) {
                                    continue search;
                                }
                            }
                        }
                        System.out.println("YES");
                        continue testCase;
                    }
                }
            }
            System.out.println("NO");
        }
    }
}