BOJ 7038 Cow Patterns

문제 링크:

문제 내용

1 이상 $S$ 이하의 정수로 이루어진 길이 $N$의 수열 $a_1, a_2, \cdots, a_N$과 길이 $K$의 패턴 $b_1, b_2, \cdots, b_K$이 있습니다. 수열에서 다음의 조건을 충족하는 길이 $K$의 부분 문자열의 위치들을 모두 찾아 출력하세요.

• 부분 문자열 $[a_i, a_{i+1}, \cdots, a_{i+K-1}] = [c_1, c_2, \cdots, c_K]$가 있을 때, 모든 $1 \le x, y \le K$에 대해 다음이 성립합니다.
  • $c_x = c_y \Leftrightarrow b_x = b_y$
  • $c_x < c_y \Leftrightarrow b_x < b_y$
  • 즉, 수열에서의 pairwise 대소관계와 패턴의 pairwise 대소관계가 모두 일치합니다.

입력

첫 줄에 $N$, $K$, $S$가 주어집니다. ($1 \le N \le 100\;000$, $1 \le K \le 25\;000$, $1 \le S \le 25$)

다음 $N$줄에는 수열의 원소들이 한 줄에 하나씩 주어집니다.

다음 $K$줄에는 패턴의 원소들이 한 줄에 하나씩 주어집니다.

출력

첫 줄에는 문제의 조건을 충족하는 각각의 부분 문자열의 개수를 출력합니다. 다음 줄부터는 각 부분 문자열의 맨 왼쪽 원소의 인덱스를 한 줄에 하나씩 오름차순으로 출력합니다.

문제 풀이