ascode.org discuss3

Description

아래는 특정 패턴을 고속으로 검색하기 위한 코드를 구현하는 방법이다.
기존의 방식은 앞에서 부터 순차적으로 탐색을 했던 것에 반해,
아래의 방법은 뒤에서 부터 비교하여 탐색을 실패 했을 경우 가능성이 없는 부분을 빠르게 생략할 수 있다.

아래의 구현 방법을 참고하여 숫자열에서 특정 패턴이 존재하는지 확인하는 코드를 작성한다.

-- [ 아 래 ] --
1. 패턴의 길이 확인
2. 패턴을 보고 스킵 테이블 작성
패턴 문자들의 skip 배열 값(패턴 마지막 문자는 제외) : (패턴 문자열의 길이 - 1) - 각 패턴 문자의 인덱스

패턴 마지막 문자의 값인 경우 앞의 문자를 확인하며 비교를 수행 해야 함으로 skip값 없음

ex) 1, 2, 3, 4, 5의 skip 배열

Patturn	1	2	3	4	5	else
skip	4	3	2	1	-	5

3. 패턴의 길이의 끝에서 부터 숫자열 탐색

일치하지 않는 경우(상), 일치하지만 마지막 글자가 아닌 경우(하)

만약 패턴의 끝 문자인 경우 앞으로 이동하며 문자열 비교

4. 앞서 정의한 스킵 테이블에 따라 확인하는 idx값을 조정
이후 3으로 이동
5. 숫자열의 끝까지 도달하였으나 탐색에 실패한 경우 해당 숫자열에는 일치하는 패턴이 존재하지 않음

Input

testcase 가 들어온다
testcase 만큼 [아래]의 입력이 반복된다

-- [ 아 래 ] --
숫자열의 길이가 입력된다
공백을 기준으로 하는 숫자열이 들어온다 숫자열의 길이는 1,000,000자를 넘지 않으며, 각 원소는 0~1000 이내의 정수이다
Pattern의 길이가 입력된다. 길이는 1000이내의 정수이다.

공백을 기준으로 하는 Pattern 숫자열이 입력된다. 이때 Pattern의 원소는 중복이 존재하지 않는다. 각 Pattern의 원소는 0~1000 이내의 정수이다

Output

일치하는 숫자열이 있으면 true 없으면 false를 출력하자

Sample Input Copy

5
6
1 2 3 4 5 6
3
1 2 3
6
1 2 3 4 5 6
3
2 3 4
6
1 2 3 4 5 6
3
1 3 5
6
1 2 3 4 5 6
3
1 2 4
6
1 2 3 4 5 6
3
4 5 6

Sample Output Copy

true
true
false
false
true

HINT

https://lksa4e.oopy.io/55d2a3e7-d320-4e40-854e-db0f4a20efbc

Source/Category

tomorrow9913