Is substr function O(n)? Is that the reason why each check is O(nm)?
According to http://www.cplusplus.com/reference/string/string/substr/, the answer is Yes.
