I firstly give a brute force solution that runs O(mn) time, which is clearly too slow, and then I give some modifications by cutting branches and eliminating redundant calculations, but still it doesn't make any significant difference on the time complexity. I didn't do this problem well. After the interview I found that there are classic algorithms to solve this problem in linear time, such as KMP and Boyer-Moore, etc.