페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8173
서브태스크

승리 유전자 1s 1024MB

문제

수년 동안 게임을 주최하면서 민재가 계속 1위를 차지하는 모습을 본 시윤이는 이것이 단순한 우연이 아니라고 결론지었다. 대신, 민재의 DNA에 "승리"가 암호화되어 있다고 생각하며, 그는 이 "승리" 유전자를 찾기 위한 과정을 설계했다.

그는 민재의 유전체를 문자열 S (길이 N)로 표현한다. 그는 어떤 쌍 (K, L)을 선택한다. 여기서 1 ≤ L ≤ K ≤ N이며, "승리" 유전자 후보는 길이가 L이고 더 큰 길이 K의 서브스트링 안에서 발견된다. 유전자를 식별하기 위해, 그는 S의 모든 길이 K의 서브스트링을 선택한다. 이를 k-mer라고 부른다. 각 k-mer에 대해, 그는 길이 L의 서브스트링 중 사전적으로 가장 작은 서브스트링을 "승리" 유전자 후보로 선택하고 (동점이 발생하면 가장 왼쪽의 서브스트링을 선택한다), 이 서브스트링이 S에서 시작하는 0-인덱스 위치 p_i를 집합 P에 기록한다.

아직 K와 L을 선택하지 않았기 때문에, 시윤이는 모든 (K, L) 쌍에 대해 후보가 몇 개 나오는지 알고 싶어 한다.

각 v\ (1 ≤ v ≤ N)에 대해, |P| = v인 (K, L) 쌍의 개수를 구하라.


입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 3000)
두 번째 줄에 문자열 S가 주어진다. 모든 문자는 대문자로 이루어져 있으며 s_i는 A-Z이다.


출력

각 v\ (1 ≤ v ≤ N)에 대해 |P| = v인 (K, L) 쌍의 개수를 한 줄에 하나씩 출력한다.


부분문제

번호 점수 조건
#125점

N≤100

#235점

N≤500

#340점

추가 제약 조건 없음


예제 

8
AGTCAACG
11
10
5
4
2
2
1
1

이 테스트 케이스에서 출력의 세 번째 줄은 5다. 이는 세 개의 "승리" 유전자 후보를 가지는 (K, L) 쌍이 정확히 5개라는 것을 의미한다. 이 후보들은 다음과 같다. (여기서 p_i는 0-인덱스 기준이다):

  • (4,2) -> P = [0,3,4]

  • (5,3) -> P = [0,3,4]

  • (6,4) -> P = [0,3,4]

  • (6,5) -> P = [0,1,3]

  • (6,6) -> P = [0,1,2]

(4,2)가 이러한 결과를 어떻게 도출하는지 살펴보자. 모든 길이 4의 서브스트링(4-mer)을 구하면 다음과 같다:

  • AGTC

  • GTCA

  • TCAA

  • CAAC

  • AACG

각 4-mer에 대해, 길이 2의 서브스트링 중 사전적으로 가장 작은 서브스트링을 식별하면 다음과 같다:

  • AGTC -> AG

  • GTCA -> CA

  • TCAA -> AA

  • CAAC -> AA

  • AACG -> AA

이 서브스트링들이 원래 문자열에서 시작하는 위치를 집합 P에 추가하면 P = [0,3,4]가 된다.

반면, (4,1) 쌍에 주목하면 총 두 개의 "승리" 유전자 후보만 만들어진다. 모든 길이 4의 서브스트링을 구하고 길이 1의 서브스트링 중 사전적으로 가장 작은 값을 식별하면 다음과 같다:

  • AGTC -> A

  • GTCA -> A'

  • TCAA -> A'

  • CAAC -> A'

  • AACG -> A'

마지막 세 경우에서 A'와 A*는 사전적으로 가장 작지만, 가장 왼쪽의 서브스트링이 우선되므로 A'만 후보로 계산된다. 따라서 P = [0,4]가 된다.



출처

USACO 2024 US Open Silver

로그인해야 코드를 작성할 수 있어요.