HMMT 二月 2017 · 团队赛 · 第 4 题
HMMT February 2017 — Team Round — Problem 4
题目详情
- [ 35 ] Let w = w w . . . w be a word. Define a substring of w to be a word of the form w w . . . w w , 1 2 n i i +1 j − 1 j for some pair of positive integers 1 ≤ i ≤ j ≤ n. Show that w has at most n distinct palindromic substrings. For example, aaaaa has 5 distinct palindromic substrings, and abcata has 5 ( a, b, c, t, ata ).
解析
- [ 35 ] Let w = w w . . . w be a word. Define a substring of w to be a word of the form w w . . . w w , 1 2 n i i +1 j − 1 j for some pair of positive integers 1 ≤ i ≤ j ≤ n. Show that w has at most n distinct palindromic substrings. For example, aaaaa has 5 distinct palindromic substrings, and abcata has 5 ( a, b, c, t, ata ). Proposed by: Yang Liu For each palindrome substring appearing in w , consider only the leftmost position in which is appears. I claim that now, no two substrings share the same right endpoint. If some two do, then you can reflect the smaller one about the center of the larger one to move the smaller one left.