Default [Q] Help! some rogue app is sending messages to my contacts

im running avast and lookout premium and they cant find anything! ive looked through running apps and cant find anything obviously amiss. its sending messages like "do you know this hot sl*tty bird? then with some dodgy link i havent clicked on. i havent downloaded any apps recently but i surf a lot on my phone so maybe a dodgy site i went to? the messages it sends are not showing up on my phone, the people im sending them to are showing me.
i have a goodybag with texts so currently not a major problem for me, more for my contacts, but im flying to australia tomorrow so will be a MAJOR problem then. Can someone pleeeease save me? I have apps that i have had a longgg time on an email address i cant access anymore so dont want to factory reset as ill lose them forever.

i found a shortcut on my phone to an app named liiiioioo l kk Pl l.ioin l oii
im tempted to delete that but im sure thats just a shortcut right? went through manage apps and no app i have named this. Cant really do the limit privelages to apps one by one as i get no notification when they send a msg so hard to police like that.

thanks in advance!!
nick