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 jfor some pair of positive integers 1 ≤ i ≤ j ≤ n. Show that w has at most n distinct palindromicsubstrings.
For example, aaaaa has 5 distinct palindromic substrings, and abcata has 5 ( a, b, c, t, at a ).
解析
英文解析
- [ 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 jfor some pair of positive integers 1 ≤ i ≤ j ≤ n. Show that w has at most n distinct palindromicsubstrings.
For example, aaaaa has 5 distinct palindromic substrings, and abcata has 5 ( a, b, c, t, at a ).
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 reflectthe smaller one about the center of the larger one to move the smaller one left.