1234567890
0987654321
1111111111
1111111111
2222222222

876543
111111
111111

#### 輸入格式

R、r、C、c的範圍在1到1000之間(包含1和1000)，且r不超過R，c不超過C。

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

7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137

#### 參考答案

```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];
for (int i = 0; i < patternLength_dec; ++i) {
final int index = (int) pattern[i];
}
final char specialChar = pattern[patternLength_dec];
final int specialShift = badCharShiftMap[(int) specialChar];

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