返回题库

HMMT 二月 2017 · 团队赛 · 第 4 题

HMMT February 2017 — Team Round — Problem 4

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [ 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 ).
解析

英文解析

  1. [ 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.