LCC '18 Contest 5 S4 - Copy/Paste

View as PDF

Submit solution

Points: 12
Time limit: 2.0s
Memory limit: 128M

Problem type

Kasia likes to watch Netflix by connecting her laptop to the TV and using a wireless mouse to browse the catalog of shows. Sometimes, she wants to search for a specific show, however she does not want to stand up and walk over to her laptop to use the keyboard. Instead, she has come up with a brilliant way to type with her mouse using the copy and paste commands.

To search for the show she wants, she selects some text from a source string on the screen that forms a prefix of her search string and then pastes the text into the search box. She repeats this with the remainder of the search string until she has typed out the complete string.

This process takes a long time, so Kasia would like to minimize the number of times she has to copy/paste something.

Input Specification

The first line of input contains two integers \(N, M\) \((1 \le N, M \le 200,000)\), the length of the source string and search string, respectively. The next line contains a string of N lowercase letters representing the source string. The third line contains a string of \(M\) lowercase letters representing the search string. It is guaranteed that you can form the search string using the process described above.

For 40 of the 100 points, \(N, M \le 5,000\).

Output Specification

Output the minimum number of copy/paste actions required to form the search string from the source string.

Sample Input 1

2 4

Sample Output 1


Sample Input 2

15 9

Sample Output 2