in case you use string matching + dynamic programming. it's O(nm) ,
even m is only 6, the over head is too big for this 2 sec time limit.

so use an automaton instead.