Nutter is a weird kid. As an infant, he was obsessed with the prefixes of
n), but hated the word
nutt itself. When his parents bought him a box of Scrabble, he realized that the board already contained a single word:
putt, which got him thinking. He wondered how he could add, swap, or remove blocks from a word ~A~ to make all the prefixes of another word ~B~.
Nutter has access to an infinite supply of Scrabble blocks, and can only add, swap, or remove blocks to form his desired prefixes. Each operation takes 1 move, but since he's quick with his hands, he isn't worrying about shifting blocks (you can add, swap, or remove non-terminal blocks). Nutter wants to know how he can turn word ~A~ into word ~B~'s prefixes (not including word ~B~ itself) using the minimum number of moves.
Subtask 1 [20%]
~1 \le N, M \le 10~
Subtask 2 [80%]
~1 \le N, M \le 10\,000~
The first line of input will contain two integers ~N~ and ~M~ separated by a single space. The second line will contain a single string ~A~ of length ~N~, and the third line will contain a single string ~B~ of length ~M~.
Output a single integer representing the minimum number of moves to change word ~A~ to all of word ~B~'s prefixes.
4 4 nutt putt
The prefixes of
p, and Nutter wants to try and make them all from the word
nutt, swap the
n with a
p and remove a
t from the end (2 operations).
pu, do the same operations as
put, but remove another
t (3 operations + 2 = 5 total).
p, do the same operations as
pu, but remove the
u at the end (4 operations + 5 = 9 total).
Since Nutter doesn't want to make
putt itself, he uses 9 operations in total.