If you are willing to settle for expected instead of worst case time, there are many string-related algorithms that are O(m/n). Intuition is that as the string size grows it's "more likely" to have some property on expectation.