ML on dataset with heavy dependency on prefix I have a target function, which heavily depends on vector prefix:

(1, 2, 0, 0, 1, 2, 4) -&gt; A
(1, 2, 0, 55, 1, 99, 1) -&gt; A
(1, 2, 124, 55, 1, 99, 71) -&gt; A
(1, 3, -5, 0, 1, 2, 4) -&gt; B
(1, 3, 12, 55, 1, 99, 1) -&gt; B
(1, 3, 124, 55, 1, 99, 71) -&gt; C
(1, 3, 124, 21, 10, 195, 11) -&gt; C
...

Prefix length may vary.
pre-condition: a training set of vectors and their target values
target: to be able to evaluate target value on arbitrary vector
I have tried HMM, but it doesn't seem to work well in this case. What algorithm should I use instead?
Consider LSTMs. They're a type of recurrent neural network that are generally very good at sequence prediction tasks and have the ability to learn very long range dependencies like you describe. 

Andrej Karpathy gives a tremendously great intro to RNN/LSTM on his blog.

Although going as far as a neural network opens up a whole new range of problems, such as long training time and finding the right architecture and gradient descent parameters. If your problem is very dependent on only a handful of terms then you may be able to get adequate results with a tabular multinomial regression approach and some smart encoding of your sequence. Something like:

y prefix1 prefix2 prefix3 has1 has2 has3  ...
A       1       2       0    1    1    0  ...
B       1       3      -5    1    0    1  ...