Hint.

[Zibri]

If you want a hint, try to implement it not on a note basis, but on a chord basis...
Use for example guitar tabs documents and use the markov algorithm to generate sequences of chords based on a database of many songs of the same genre. The results will be astonishing.