# Tag Info

1

Simply note that KMP is incremental: it finds the longest PS (also known as border) for every prefix of the string. If you don't throw away that information, you don't need to re-run KMP for every prefix.

1

Suppose there are $c$ types of balls, and there are $n_i$ balls of type $i$. Let $S$ be a set of types of balls. In how many ways can we choose balls so that only balls of type $S$ appear, and at least one ball of type $i$ appears for each $i \in S$? The answer is clearly $$\prod_{i \in S} (2^{n_i} - 1).$$ Taking $S = \{1,\ldots,c\}$, we get a solution to ...

1

You should consider (one of) the word $w$ of minimal length in $S$, and show that for this word in particular, you can reach the conclusion that $|l| = 0$.

Top 50 recent answers are included