More questions about permutations
Re your question 1: Guillemot and Marx, "Finding small patterns in permutations in linear time", SODA 2014 solves these problems in linear time, and more generally gives a linear time recognition algorithm for every fixed permutation class with a finite basis.

I don't know of an answer for question 2 (when the subpattern may be variable in size).