966. Words Made Only of Other Words

You are given n distinct words. Print the ones that can be written as a concatenation of TWO OR MORE words taken from the same list, in alphabetical order, one per line. Words may be reused. Print none if no word qualifies.

cat cats dog catsdog dogcat rat -> catsdog, dogcat a aa aaa -> aa, aaa ab abab -> abab ab cd ef -> none

The second line shows reuse: aa is a + a, and aaa is a + a + a or a + aa. Either decomposition is enough.

## Why the word itself is never a problem

Every piece is a listed word and there are at least two of them, and every word has at least one letter, so every piece is strictly SHORTER than the word being built. A word can therefore never be one of its own pieces, and no exclusion step is needed anywhere in the program. That is worth establishing before writing any code, because guarding against it by hand is where this problem usually goes wrong.

## Why the natural table gives the wrong answer

The obvious table is ok[i], meaning "the first i letters can be built". It is the table of problem 960 and of problem 513, and it says nothing about how MANY pieces were used. Every word in the list satisfies ok[length] trivially, using itself as one piece, so the answer would be "all of them".

Track the LARGEST number of pieces instead.

for each word x: best[0] = 0, every other best[i] = -1 # -1 means unreachable for i in 0 .. length(x)-1: if best[i] < 0: skip node = root for j in i .. length(x)-1: if child[node][x[j]] is absent: break node = child[node][x[j]] if isEnd[node]: best[j+1] = max(best[j+1], best[i] + 1) x qualifies if best[length(x)] >= 2

## Why the maximum is the right thing to maximise

The question asks whether SOME decomposition uses two or more pieces. A minimum would answer a different question and would usually be 1, from the word itself. The maximum over all decompositions is at least 2 exactly when some decomposition has at least 2 pieces, which is the condition, so maximising is not a heuristic here but a restatement.

The recurrence is sound for the maximum for the same reason it is for the minimum: any decomposition of the first j+1 letters ends in one listed word occupying x[i..j], and everything before it is a decomposition of the first i letters, so the piece count is best[i] + 1 at most, and every best[i] + 1 is achievable.

## The inner walk

The inner loop is problem 959's: step down the trie one character at a time from the start i and take every marked node. No substring is built and no hash is computed, and the walk stops as soon as no listed word can continue, so a start with no continuation costs one step.

## The output

Alphabetical order, each qualifying word once. The input order is not alphabetical, so a sort belongs at the end, and none rather than an empty output when nothing qualifies.

## Cost

Building is O(total characters), at most 1 + 50000 nodes. Each word costs O(length^2) steps in the worst case, so the whole run is bounded by the total length times the longest word, 50000 * 50 = 2500000 steps. Nothing overflows: a piece count is at most the word length, which is 50.

Constraints - `1 ≤ n ≤ 2000` - Every word is 1 to 50 lowercase English letters. - The words are pairwise different and total at most 50000 characters. - A word may be used any number of times inside a concatenation.