題目描述

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



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

1234567890
0987654321
1111111111
1111111111
2222222222

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

876543
111111
111111

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

原題網址

https://www.hackerrank.com/challenges/the-grid-search

輸入格式

第一行為測試資料的數量T,範圍在1到5之間(包含1和5)。
接下來的T組資料的每個第一行為圖形G列數R和行數C。
再來的R行輸入所有列的圖形資料。
接著輸入樣本P的列數r和行數c。
再來的r行輸入所有列的樣本資料。
R、r、C、c的範圍在1到1000之間(包含1和1000),且r不超過R,c不超過C。

輸出格式

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

範例輸入

2
10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530
15 15
400453592126560
114213133098692
474386082879648
522356951189169
887109450487496
252802633388782
502771484966748
075975207693780
511799789562806
404007454272504
549043809916080
962410809534811
445893523733475
768705303214174
650629270887160
2 2
99
99

範例輸出

YES
NO

額外解釋

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

7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137

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

解題概念

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

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

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

https://magiclen.org/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> resultList = 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) {
                resultList.add(starePointer + 1);
                if (sourcePointer > sourceLength_dec || limit > 0 && resultList.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;
            }
        }

        final Integer[] array = new Integer[resultList.size()];
        resultList.toArray(array);
        return array;
    }

    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");
        }
    }
}