ML on dataset with heavy dependency on prefix
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  ...