Question 63
Let $w = w_{1} w_{2} \ldots w_{n}$ be a word. Define a substring of $w$ to be a word of the form $w_{i} w_{i+1} \ldots w_{j-1} w_{j}$, for some pair of positive integers $1 \leq i \leq j \leq 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$).
For example, aaaaa has 5 distinct palindromic substrings, and abcata has 5 ($a, b, c, t, ata$).