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 (a.k.a. -1).↵
↵
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!↵
↵
EDIT: Note that chosen substrings can overlap. I put some cases below.↵
↵
Input 1:↵
abcbcd↵
abcd↵
Output 1:↵
2↵
↵
Input 2:↵
iamsmart↵
iamdumb↵
Output 2:↵
-1↵
↵
Input 3:↵
asmallmallinmalta↵
atallmallinlima↵
Output 3:↵
5↵
↵
Explanations: "abcd" = "ab" + "cd", no "d"s in the first string of Input 2, "atallmallinlima" = "a" + "ta" + "llmallin" + "li" + "ma"
↵
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!↵
↵
EDIT: Note that chosen substrings can overlap. I put some cases below.↵
↵
Input 1:↵
abcbcd↵
abcd↵
Output 1:↵
2↵
↵
Input 2:↵
iamsmart↵
iamdumb↵
Output 2:↵
-1↵
↵
Input 3:↵
asmallmallinmalta↵
atallmallinlima↵
Output 3:↵
5↵
↵
Explanations: "abcd" = "ab" + "cd", no "d"s in the first string of Input 2, "atallmallinlima" = "a" + "ta" + "llmallin" + "li" + "ma"
