[Solution] Text Editor solution codeforces

Text Editor solution codeforces – You wanted to write a text 𝑡t consisting of 𝑚m lowercase Latin letters. But instead, you have written a text 𝑠s consisting of 𝑛n lowercase Latin letters, and now you want to fix it by obtaining the text 𝑡t from the text 𝑠s.

Table of Contents

[Solution] Text Editor solution codeforces

Initially, the cursor of your text editor is at the end of the text 𝑠s (after its last character). In one move, you can do one of the following actions:

  • press the “left” button, so the cursor is moved to the left by one position (or does nothing if it is pointing at the beginning of the text, i. e. before its first character);
  • press the “right” button, so the cursor is moved to the right by one position (or does nothing if it is pointing at the end of the text, i. e. after its last character);
  • press the “home” button, so the cursor is moved to the beginning of the text (before the first character of the text);
  • press the “end” button, so the cursor is moved to the end of the text (after the last character of the text);
  • press the “backspace” button, so the character before the cursor is removed from the text (if there is no such character, nothing happens).

Your task is to calculate the minimum number of moves required to obtain the text 𝑡t from the text 𝑠s using the given set of actions, or determine it is impossible to obtain the text 𝑡t from the text 𝑠s.

You have to answer 𝑇T independent test cases.

[Solution] Text Editor solution codeforces

The first line of the input contains one integer 𝑇T (1𝑇50001≤T≤5000) — the number of test cases. Then 𝑇T test cases follow.

The first line of the test case contains two integers 𝑛n and 𝑚m (1𝑚𝑛50001≤m≤n≤5000) — the length of 𝑠s and the length of 𝑡t, respectively.

The second line of the test case contains the string 𝑠s consisting of 𝑛n lowercase Latin letters.

The third line of the test case contains the string 𝑡t consisting of 𝑚m lowercase Latin letters.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 50005000 (𝑛5000∑n≤5000).

[Solution] Text Editor solution codeforces

For each test case, print one integer — the minimum number of moves required to obtain the text 𝑡t from the text 𝑠s using the given set of actions, or -1 if it is impossible to obtain the text 𝑡t from the text 𝑠s in the given test case.

Example
input

Copy
6
9 4
aaaaaaaaa
aaaa
7 3
abacaba
aaa
5 4
aabcd
abcd
4 2
abba
bb
6 4
baraka
baka
8 7
question
problem
output

Copy
5
6
3
4
4
-1

 

For Solution

Click Here

Leave a Comment