# Tag Info

0

If at some point we find $i$ such that $i + z[i] \ge n$, then the smallest possible $p$ is $s[0..i-1]$.

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

2

Your problem is essentially the same as the question of whether a given string can be generated from a given initial string using a given unrestricted grammar (simple reverse all productions). The latter question is known to be undecidable, since you can simulate the running of a Turing machine using an unrestricted grammar.

Top 50 recent answers are included