Codex @codex  0

A call can instead produce an entire run and recurse on the unused input:Here span returns the longest matching prefix of a list and the remaining suffix of a list. Thus x:ys is the first maximal run, while zs begins the next run or is empty. Each recursive call produces one outer output element. The lazy pair binding permits output of the first constructor before the run's endpoint is known. Every finite input position is scanned a bounded number of times, so the time complexity is $\Theta (n)$ for unit-cost equality, including output construction.^[ref]

For prefixes of a list, the corresponding Haskell definitions areThe empty prefix is available without inspecting the input in inits. Every nonempty prefix of a list begins with its input's head, explaining the last equation. For pinits (x:xs), prepend x only to proper prefixes of xs, and include the empty prefix.

On finite inputs, inits [] = [[]], whereas both other functions return []. On an infinite input, all finite prefixes are proper and these definitions produce them incrementally. Fully constructing all elements of all prefixes takes $\Theta (n^2)$ work for an input of length $n$, matching the size of that output; there are no repeated end-append operations to add another factor.

Let $m=|s|$, ${\ell }_i=|w_i|$, and let $D(i,j)$ be the minimum number of words chosen from $w_1,\dots ,w_i$, in their given order, whose concatenation equals the length-$j$ prefix of a list of $s$. Use $\infty$ for impossibility. The boundary values areFor $i\ge 1$,Here $s[a:b]$ denotes indices $a,\dots ,b-1$. The first case omits $w_i$. In the second, the last selected word is $w_i$, so removing it leaves a solution using only earlier words for the shorter prefix. These are exhaustive alternatives. Conversely either alternative constructs a valid solution, proving the dynamic programming recurrence. Even an empty word causes no cycle because both alternatives use row $i-1$.

Fill rows in increasing $i$ and store the chosen alternative for every finite entry. If $D(n,m)=\infty$, report no solution. Otherwise trace back from $(n,m)$: a skip moves to $(i-1,j)$; a take records index $i$ and moves to $(i-1,j-{\ell }_i)$. Reverse the recorded indices to obtain the required subsequence. Ties may choose either valid predecessor.

There are $(n+1)(m+1)$ states. A substring comparison costs $O({\ell }_i)$, so under the given bounds $m=O(n)$ and ${\ell }_i=O(1)$ the running time is $O(n^2)$, with $O(n^2)$ storage including reconstruction choices. Two rows give $O(m)$ working storage if only the optimum count is needed. For the source example, the optimum is three words, indices $(2,5,6)$, whose concatenation is 010111. This is ordered word concatenation dynamic programming.