Complexity of ambiguous parsing? Consider the following problem. We are given a set of words $W \subseteq \Sigma^*$ and a set of sentences $S \subseteq W^*$. The "ambiguous parsing" problem consists, given a word $w \in \Sigma^*$, to enumerate the sentences $s \in S$ that parse to $w$ (meaning that $s$ consists of the letters $w_1,\ldots,w_k$ and $w$ is the concatenation of the corresponding words).

The problem has an interesting variant which is the search of spoonerisms: we now allow some number $M$ of letters swap, and we want to enumerate the valid sentences obtainable from $w$ with at most $M$ swaps.

So my question is: under what condition on the language $S$ can the above  problem be solved in linear time? By this I mean time $O(|W|+|S|+|w|+c)$ where $c$ is the number of solutions.

(NOTE ADDED: in response to the comments below, the vocabulary $W$ is assumed to be finite, and the set $S$ can be infinite but "finitely described" by some device $\Delta_S$. As we can report all meaningful subwords of $w$ in $O(|w|)$ time, it may be possible to reduce my question to the enumeration of the accepting paths of a non-deterministic automaton or the derivations of an ambiguous grammar. What I am looking for is restricted models that allow a linear or amortized-constant delay enumeration of the parsings.)
Here is the first part of the answer (without swapping).  I restated some of the definitions to make them clearer (I think), as I was somewhat confused by the statement of the question.

Introduction to the problem and its practical importance

I do not know the motivation for the question, as it was not given.
However this is a known problem of natural language processing (NLP),
and specifically of speech processing. The problem is that phonems are
not always clearly identifiable, nor are the boundaries between
lexical elements (words), which is a little bit more general than the
question. As a consequence, there can be several ways to cut the
spoken sentence into words of the language. In order to account for
that, the single linear stream of phonems is actually transformed into
what is called a "word lattice" which may be seen as a
directed acyclic graph or as an acyclic DFA (though even the
acyclicity is also a topic for discussion in some cases - see my
remark on whether the empty word can be in $W$). This word
lattice corresponds to all the ways the sentence can be cut into
recognizable words. This is often based on probabilities and Markov
models.

Well known examples of the need for word lattices are holorime
verses. See for example "Phonological ambiguity that changes the syntactic structure".

The word lattices are then used in various way for further linguistic
processing. One use is to do syntax analysis with respect to a
syntactic definition of the language, the identified lexical elements
(or their lexical category, called "part of speech") being used as
alphabet symbols at that syntactic level. In the question asked, the
collection $S$ or sentences plays the role of the language syntax that
defines allowed sentences. The set $W$ is the collection of acceptable
spoken language words that can be built from the phonems in $\Sigma$.
It is a bit simplified from the real speech processing situation. For
example, the set $W$ is finite, while in speech processing it is
considered open (actually finite, but so large ...). This is dealt with
by replacing all the words of a given category by that category
considered as a whole (I skip many details).

Many modern parsing techniques can be readily extended to the parsing
of word lattices, as most syntactic formalisms are closed under
intersection with regular sets. See for example "Recognition can be
Harder than Parsing".

The problem addressed by word lattices (and by this question) is lexical
ambiguity: the ambiguity resulting from the fact that the sequence of
lexical elements that can correspond to the analyzed string is not
unique. This can be opposed to syntactic ambiguity du to the fact that the
lexical sequence can be generated syntactically in two different ways,
as in ambiguous context-free grammars.

The issue of character swapping, here supposedly to detect
"spoonerisms", is part of various techniques to deal with input
ill-formedness that can be modeled by finite state tranducers.
Here again, closure properties are more than helpful.

A solution without swap, linear in each parameter

The set $W$ may be considered finite, as only a finite number of words
in $W$ can be used to form the alphabet for sentences. We assume
furthermore that the empty word is not in $W$. It is not strictly
necessary for the construction given here, but it could make the
parsing yield an arbitrarily long sequence, independently of the
length of the string $w$ being parsed, possibly giving a false idea of
the complexity.

We associate with each word $w\in W$ a unique symbol $\hat w$. Let
$\hat W=\{\hat w \mid w\in W\}$. This is not strictly necessary, but may
avoid confusion as to what is the alphabet.

Then you build a trie, as a DFA that recognizes the words in $W$. Each
final state recognizing a word $w_k\in W$ is then labeled with $\hat w_k$
(cf Moore machines). Then an $\epsilon$-transition is added from each
final state to the initial state, turning the DFA into a NFA that
recognizes sequences of words in $W$, and which can output $\hat w_k$
whenever $w_k$ has been recognized. Then you apply the powerset
construction to turn this NFA into a DFA $T_W$, such that the states of this new
DFA have all the labels of the trie final states they contain.

This construction, though expensive because of the powerset
construction, is done only once, independently of the sentence $w$,
and thus does not count in the complexity analysis. It is amortized over all string $w$ that will be parsed (as is the case for all parser construction techniques).

Given a string  $w\in\Sigma^*$
you build a DFA $L_{W,w}=(\{q_i\mid 0\leq i\leq |w|\},\hat W,q_0,q_n,\tau_{W,w})$ as follow:


$q_0$ and $q_n$ are respectively initial and final state
the number of states is $n+1$
there is a transition on input $\hat w_k$  from state $q_i$ to state
$q_j$ iff $w[i:j]=w_k$ where $w_k \in W$


The notation $w[i:j]$ denote the substring of $w$ from index $i+1$ to
index $j$, the first letter having index $1$.

This finite state automaton $L_{W,w}$, called a word lattice in speech
processing, generates or recognizes all sentences that are sequences
of words in $W$ that concatenate into the string $w$. Note that the literature often presents it as a directed acyclic graph rather than a DFA.

To build the transitions, you apply the DFA $T_W$ to the string
$w$. Whenever you enter a state that has a label $\hat w_k$ (It may
have several labels), it means
that you have just recognized the string $w_k\in W$. If you have read
$j$ letters, it means that $w[i:j]=w_k$ for $i=j-|w_k|$. Thus you add
the corresponding transition to the word lattice.

The DFA $T_W$ executes no more than $|w|$ transition steps, and at
each step adds at most $|W|$ transitions to the word lattice.
Hence the complexity is $O(|W|\times|w|)$

Now we have to find out which sentences in the language recognize by
the language of $L_{W,w}$ are also recognized by the DFA $M_S$ on alphabet
$\hat W$ recognizing $S$.

In other words we want the intersection of the two languages. This can
be obtained by the usual cross product construction of the two
automata, which are both DFA. The resulting automaton is a recognizer
for the solutions, and can be used to generate them non
deterministically.

Since the set $S$ is a regular set, potentially infinite, each
solution must be given explicitely as a word in $\hat W^*$, with
corresponding cost, rather than being named in constant time.
However, if the empty word is not in $W$, the length of each solution
is bound by the length of $w$.

The cross product construction gives a number of states that is the
product of that number for each automaton: $|Q_S|\times(|w|+1)$.
Each of the $|\tau_S|$ of the DFA $M_S$ is associated with each of the
$O(|W|\times|w|)$ transitions of the word lattice to determine the
transitions of the cross product.

Hence the cost of producing the DFA for the solutions is $O(|W|\times|w|\times|M_S|)$

The cross-product DFA is noted $F_{W,S,w}$. Its construction is such
that its mimics exactly the DFA $S$, but only for the sentences in
$\hat W^*$ accepted by the word lattice, i.e. all those corresponding
to the sentence $w$. Hence, it does give all the sentences in $S$ as
words in $\hat W^*$ that are equal letter-wise to $w$.

Enumerating the solutions

Here is how you can enumerate the solutions with the DFA $F_{W,S,w}$
to be conformant to the constraint that the enumeration should be
linear in the size of a trie of all solutions.

We suppose the symbols in $\hat T$ are totally ordered, for example by
the lexicographic order of the corresponding words in $T$.  We also
assume that the DFA $F_{W,S,w}$ has been pruned of all states that do
not have a path to an accepting state, and of transitions to and from
these states (this does not have to exceed the cost of building the
DFA). The missing transitions will be considered as virtually going to
a dead state; they are not needed here.

Let $d$ be the length of the string $w$. Since we
excluded the empty word from $T$, all solutions have a length less
than $d$. Hence the DFA $F_{W,S,w}$ is acyclic, i.e. represented by an
edge labeled DAG. 

Initialize an array $\mathcal S$ of length $d$, indexed from 1 to $d$, storing
the words to be enumerated, and a cursor $c$ indexing the last
modified letter of $\mathcal S$.

Initialize a second array $\mathcal Q$ of length $d+1$, indexed from 0
to $d$, storing the states followed to produce/recognize the current
content of $\mathcal S$. The cursor $c$ indexes also the last visited
state.The array $\mathcal Q$ is initialised with the initial state of
the DFA $F_{W,S,w}$ at index 0.

Both arrays are used as pushdown stacks, the cursor $c$ pointing at
the top.

Then perform a simulation of a Depth First Search (DFS) on a virtual
version of the trie of all solutions recognized by the DFA
$F_{W,S,w}$, by updating only the top of the stacks.

When a transition of the DFA is followed, its label is pushed on
$\mathcal S$ and the next state is pushed on $\mathcal Q$.

When a state $q$ has just been pushed on the stack $\mathcal Q$:


If $q$ is an accepting state the content of stack $\mathcal S$ is a
solution;
if $q$ has transitions, follow the one with the smallest label;
if there are no transitions, then pop both stacks.


When the stacks are popped, let $\hat w$ be the symbol just popped
from $\mathcal S$, and $q$ be the new top of $\mathcal Q$.


if $q$ has transitions with a label greater than $\hat w$, follow
the one with the smallest label;
otherwise pop both stack.


When all transitions of the initial state at the bottom of stack
$\mathcal Q$ have been followed, the enumeration terminates.

This algorithm is essentially a virtual traversal of the trie of all
solutions, because the finite automation $F_{W,S,w}$ is deterministic
and pruned of unproductive states and transitions. Therefore the time
cost is linear in the size of that trie. The solutions are given in
lexicographic order with respect to $\hat V$.

However, though I have not explored the issue, I fear that the size of
that trie may far exceed the size of the DFA $F_{W,S,w}$. Even if S is
finite, it may be represented by a DFA that is much smaller than its
trie (precisely our problem).

Note:
$S$ does not have to be a regular set.

The essential ingredients for the solution presented and its
complexity are the deterministic real-time character of the automaton
and the cross product construction. Hence it should be applicable with
the same complexity result if $S$ were a real-time deterministic
context-free language.

More generally, all kinds of languages families may be considered,
with a complexity that depends on recognition complexity of the
family.
For example, if $S$ is a context-free language,
then the complexity for $|w|$ is at worst $O(|w|^3)$. But things get
then more complex: parsing with respect to a regular set for $S$ just
means recognizing $\hat W$-strings in $S$ that expand to the word $w$.
However, if S is a context-free language, one may be satisfied with a
recognizer as in the regular case, but one may also want to have some
or all parses with respect to a specific grammar which may itself be
ambiguous. The complexity analysis may then depend somewhat on what is
actually desired, on language properties or on grammar properties.
And this extend to a variety of other grammatical formalisms.

Allowing to swap letters

To come later. It can be done also with finite state techniques.