Do algorithms exist to find all the patterns in a word?
I would like to count all the 3-step increasing sequences (123 i.e. 123, 234 & 345) in some word in the alphabet {1,2,3,4,5} such as "51234321343221343234". I don't care about spacing, so the subword 234 is good, but 23****4 is also good.
What if I ask these subwords be disjoint? I would expect a Robinson-Schensted-like algorithm except the increasing subsequences are of a fixed length.
Do asymptotics exist in either case?
How about patterns which are not necessarily increasing like 121 (i.e. 121,232,343,454,3**4*3, etc.)?
e.g. 51234321343221343234 has 343,121, 232,343,343 with 52124 left over.
$x = (x_1,x_2,\dots,x_3)$ and $y = (y_1,y_2,\dots,y_3)$ are "equivalent up to translation" if there is a single $k$ with $y_i = x_i + k$. A "pattern" an equivalence class of words equivalent up to translation. An "occurrence" of a pattern is an ordered subset of letters in a word equivalent to the given patterns. The bold numbers in 512 3 43213 4 32213432 3 4 are an occurrence the pattern 121.