Given two non-empty strings A and B composed of lowercase Latin letters, what is the minimum number of substrings of A needed to form string B? The lengths of A and B are at most 100000. If the task is not possible for a given input, output a rogue value.

I was thinking about solving this with an O(N^2) DP, but that does not fit into the time limit of 5 seconds.

Please help, and thanks in advance!