題目描述
給一個由0~9數字組成的二維陣列,接著要使用二維的樣本嘗試在這個陣列中搜尋符合樣本的數字。
舉例來說,下面是一個二維陣列的圖形G:
1234567890
0987654321
1111111111
1111111111
2222222222
0987654321
1111111111
1111111111
2222222222
假設我們要尋找的二維陣列樣本P是:
876543
111111
111111
111111
111111
如果我們掃描原本的圖形G,我們可以發現從第二列到第四列的第三行到第八行,符合樣本P。因此可以說樣本P在圖形G裡面。
原題網址
輸入格式
第一行為測試資料的數量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
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
NO
額外解釋
第一組資料可以在圖形G內找到樣本P:
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
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的說明可以參考這篇:
參考答案
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");
}
}
}