# counting patterns in a word

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.

• If you're removing hits after finding them (as is implied by your words "left over"), then I think the number of hits is not well defined. For example, in the word 121121, if I first remove the first 1, first 2, and last 1, I am left with 211 -- no remaining hits; however, I can pick my first hit differently so as to end up with two total hits. If you're asking about the total number of (possibly overlapping) hits, then this is well defined, but what do you mean by "left over"? – Yoav Kallus Feb 3 '12 at 0:43
• there will probably never be an algorithm that finds ALL the patterns in a word, it's too general. of course you can code a program to find a lot of specific patterns, like increasing sequences, but first of all, you should define what you call "pattern": is "246" a pattern? "963"? – alberto.bosia Feb 3 '12 at 0:46
• I think "pattern" means subword order isomorphic to a given one... so "246" and "135" are in the same pattern. Well... "123" is order-isomorphic to "246". How can I be more specific? $x = (x_1,x_2,\dots,x_3)$ and $y = (y_1,y_2,\dots,y_3)$ are equivalent up to translation so $y_i = x_i + k$ for all i. I think that's closer to what I mean. – john mangual Feb 3 '12 at 0:58
• @Yoav. You are correct. Maybe we should ask for the maximum number of occurrences of a pattern in a given word. Or we could try to maximize the number letters left over :-) – john mangual Feb 3 '12 at 1:07