У меня есть подозрение, что функции работы со строками пишутся на ассемблере и используют команды процессора типа REP SCAS - надеюсь, Вы знаете, что это такое.
Проверить это можно на исходниках библиотек, благо в Linux они доступны.
Навскидку я могу Вам посоветовать заменить m_0[0] на *m_0 - хотя это вряд ли что-то изменит.
И я вообще не понял Вашего алгоритма. Такое ощущение, что Вы зачем-то сравниваете с конца.
И ещё интересно, на каких примерах Вы это тестировали. Есть тонкость - многие алгоритмы поиска подстроки сильно зависят от данных. Если строка набита случайными символами - лучший подход один; если строка содержит повторяющиеся куски - лучший подход немного совсем другой.