Нашёл хорошую реализацию с помощью регулярных выражений
Код AS3:
var te:String = "что заменяем";
var t:String = "на что заменяем";
var nt:RegExp=new RegExp('^'+te);
m.text = m.text.replace(nt, t);
как доработать код так, чтобы если есть вначале строки, то заменяем если нет то добавляем в начало строки