HMMT 二月 2017 · 冲刺赛 · 第 17 题

HMMT February 2017 — Guts Round — Problem 17

[ 10 ] Sean is a biologist, and is looking at a string of length 66 composed of the letters A, T, C, G . A substring of a string is a contiguous sequence of letters in the string. For example, the string AGT C has 10 substrings: A, G, T, C, AG, GT, T C, AGT, GT C, AGT C. What is the maximum number of distinct substrings of the string Sean is looking at?

解析

[ 10 ] Sean is a biologist, and is looking at a string of length 66 composed of the letters A, T, C, G . A substring of a string is a contiguous sequence of letters in the string. For example, the string AGT C has 10 substrings: A, G, T, C, AG, GT, T C, AGT, GT C, AGT C. What is the maximum number of distinct substrings of the string Sean is looking at? Proposed by: Yang Liu Answer: 2100 Let’s consider the number of distinct substrings of length . On one hand, there are obviously at most 4 distinct substrings. On the other hand, there are 67 − ` substrings of length ` in a length 66 string. Therefore, the number of distinct substrings is at most 66 ∑ min(4 , 67 − ) = 2100 . ` =1 To show that this bound is achievable, one can do a construction using deBrujin sequences that we won’t elaborate on here.