Sliding Window Dictionary String Matching Consider the following problem. We are given a set of patterns (strings) $\Pi = \{\pi_i\}$, a text $s$, and a window length $k$. We want a list of all shifts $0 \le i \le |s|-k$ such that every pattern in $\Pi$ is contained in the substring $s[i:i+k]$.

Can this be solved in linear- or near-linear-time? It can of course be solved in quadratic time $O(|s| |\Pi| + \sum |\pi_i|)$ using KMP or Aho-Corasick plus post-processing.

The motivation for this problem is finding matches for a topic (represented by the set of patterns) in a text. In that context it actually makes sense to require the matches to be non-overlapping so I'm also interested in that case, but it might be easier to start with the relaxed version.

I would also be interested in generalizations of the problem that allow for approximate matches of some kind, eg, only requiring a threshold on the size of the subset of matching patterns, allowing matches within given edit distance, or something using hidden Markov models or general probabilistic graphical models. I would be surprised if any such generalization can be solved in subquadratic time though.
The set of all $k$-length strings that contain every pattern in $\Pi$ is regular; call it $L$.  (It is $(\Sigma^* \pi_1 \Sigma^* \cap \dots \cap \Sigma^* \pi_m \Sigma^*) \cap \Sigma^k$.)  From this, you can form a nondeterministic finite-state automaton (NFA) that recognizes $\Sigma^* L$.  Next, convert this to a DFA.  Finally, run the DFA across the input string $s$.  You can then obtain all locations in the string where the DFA is in an accepting state; each such location  is an index $i+k$ so that $s[i:i+k]$ matches all patterns in $\Pi$.

The running time will be linear in $|s|$ and the size of the DFA.  I expect the size of the DFA to be exponential in $\Pi$ and $k$, but independent of $|s|$.  So, if you only care about the dependence on $|s|$, this algorithm might meet your requirements.  If you additionally care about the dependence on $\Pi$ and/or $k$, I do not expect this will meet your requirements.