RGPC '17 P5 - Scrabble Nuts - Olympiads Online Judge

RGPC '17 P5 - Scrabble Nuts

Points: 12 (partial)

Time limit: 1.0s

Memory limit: 64M

Authors:

Problem type

Nutter is a weird kid. As an infant, he was obsessed with the prefixes of nutt (nut, nu, and 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$ ~A~ to make all the prefixes of another word $B$ ~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$ ~A~ into word $B$ ~B~'s prefixes (not including word $B$ ~B~ itself) using the minimum number of moves.

Constraints

Subtask 1 [20%]

$1 \le N, M \le 10$ ~1 \le N, M \le 10~

Subtask 2 [80%]

$1 \le N, M \le 10\,000$ ~1 \le N, M \le 10\,000~

Input Specification

The first line of input will contain two integers $N$ ~N~ and $M$ ~M~ separated by a single space. The second line will contain a single string $A$ ~A~ of length $N$ ~N~, and the third line will contain a single string $B$ ~B~ of length $M$ ~M~.

Output Specification

Output a single integer representing the minimum number of moves to change word $A$ ~A~ to all of word $B$ ~B~'s prefixes.

Sample Input

4 4
nutt
putt

Sample Output

Explanation

The prefixes of putt are put, pu, and p, and Nutter wants to try and make them all from the word nutt.

To get put from nutt, swap the n with a p and remove a t from the end (2 operations).
To get pu, do the same operations as put, but remove another t (3 operations + 2 = 5 total).
To get 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.

Comments

2

NeatMuffin commented on Feb. 18, 2017, 2:50 a.m. ← edit 6 →

Words ARE case-sensitive.

Swap = Replace 1 character from word A WITH another character to MAKE word B.

4
percywtc commented on Feb. 17, 2017, 7:30 p.m. ← edited →
What can be swapped? Is it allowed to...

swap blocks within the word A

swap block from the word A and a block taken from the supply

Also, are the words case-sensitive?

I hope these can be clarified. Thank you.