시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 1024 MB | 16 | 9 | 9 | 69.231% |
Jaehyun makes and sells bar magnets of various lengths and colors. He makes a lot of cube-shaped "basic magnets" of the same size. The basic magnets are colored in one of the 26 colors. See Figure 1. Jaehyun makes various bar magnets according to the customers’ request by connecting basic magnets. But connecting basic magnets one by one takes quite a long time. So Jaehyun tried to save time by using a "template bar magnet" consisting of several basic magnets instead of the basic magnets. To simplify the process, Jaehyun decided to use only one type of template bar magnet and make it in bulk in advance. Now he uses the pre- made template bar magnets to produce bar magnets requested by customers. Note that the template bar magnets are polarized and cannot be connected in the opposite direction.
Figure 1 Basic Magnets
There are some rules when Jaehyun uses the template bar magnets to produce requested bar magnets. For convenience, we call the template bar magnet the T-bar.
Jaehyun wants to minimize the total time to produce the requested bar magnet using T-bars. Note that it does not matter how many T-bars Jaehyun uses.
For example, assume that the T-bar consists of 6 basic magnets as Figure 2. Assume a customer requests a bar magnet consisting of 17 basic magnets as Figure 3.
Figure 2 A T-bar consisting of 6 basic magnets
Figure 3 A requested bar magnet by a customer
In this example, the requested bar magnet can be produced using three T-bars. Consider the first T-bar. If the third (blue) basic magnet of the T-bar is replaced with a purple one, since the other basic magnets all match, the length 6 front part of the requested bar magnet can be constructed with 1 time. Next consider the second T-bar. Since the last (red) basic magnet of the bar magnet constructed so far matches the first basic magnet of the T-bar, it can be removed in 0 time. Also, if one blue basic magnet is inserted in the 9th position, the length 12 front part of the requested bar magnet can be constructed with additional 1 time. Now consider the third T- bar. Since the last (red) basic magnet of the bar magnet constructed so far matches the first basic magnet of the T-bar again, it also can be removed in 0 time. And if the 3rd (blue) and the 6th (red) basic magnets of the T- bar are replaced with grey and green one, respectively, the requested bar magnet is constructed with additional 2 time. The total time is 1+1+2 = 4, which is the minimum time to construct the requested bar magnet using the T-bars.
Given a T-bar of length $m$ and a requested bar magnet of length $n$, write a program to output the minimum time to construct the requested bar magnet using the T-bars. Each of the 26 colors of basic magnets is represented by a different uppercase alphabet. And bar magnets will be given as strings consisting of uppercase alphabets.
Your program is to read from standard input. The input starts with a line containing the T-bar represented by a string consisting of $m$ ($5 ≤ m ≤ 20$) uppercase alphabets. In the next line, the requested bar magnet is given as a string consisting of $n$ ($10 ≤ n ≤ 200\,000$) uppercase alphabets.
Your program is to write to standard output. Print exactly one line. The line should contain the minimum time to construct the requested bar magnet using the T-bars.
AACEEA AADEEAACCEEAABEEE
4
ABABCCC ABABCCABAB
4
ABABA ABABABABABABABABABA
0
BACBB DAACADCDBA
8
ABCDEABCDE ABCDEABCDEX
1