Middle-Out [codeforces 1231E] (문자열 일치 문제)

E. Middle-Out
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
The problem was inspired by Pied Piper story. After a challenge from Hooli's compression competitor Nucleus, Richard pulled an all-nighter to invent a new approach to compression: middle-out.
You are given two strings ss and tt of the same length nn. Their characters are numbered from 11 to nn from left to right (i.e. from the beginning to the end).
In a single move you can do the following sequence of actions:

choose any valid index ii (1≤i≤n1≤i≤n),

move the ii-th character of ss from its position to the beginning of the string or move the ii-th character of ss from its position to the end of the string.

Note, that the moves don't change the length of the string ss. You can apply a move only to the string ss.
For example, if s=s="test"in one move you can obtain:

if i=1i=1 and you move to the beginning, then the result is "test"(the string doesn't change),

if i=2i=2 and you move to the beginning, then the result is "etst",

if i=3i=3 and you move to the beginning, then the result is "stet",

if i=4i=4 and you move to the beginning, then the result is "ttes",

if i=1i=1 and you move to the end, then the result is "estt",

if i=2i=2 and you move to the end, then the result is "tste",

if i=3i=3 and you move to the end, then the result is "tets",

if i=4i=4 and you move to the end, then the result is "test"(the string doesn't change).

You want to make the string ss equal to the string tt. What is the minimum number of moves you need? If it is impossible to transform ss to tt, print -1.
Input
The first line contains integer qq (1≤q≤1001≤q≤100) — the number of independent test cases in the input.
Each test case is given in three lines. The first line of a test case contains nn (1≤n≤1001≤n≤100) — the length of the strings ss and tt. The second line contains ss, the third line contains tt. Both strings ss and tt have length nn and contain only lowercase Latin letters.
There are no constraints on the sum of nn in the test (i.e. the input with q=100q=100 and all n=100n=100 is allowed).
Output
For every test print minimum possible number of moves, which are needed to transform ss into tt, or -1, if it is impossible to do.
Examples
input
Copy

3
9
iredppipe
piedpiper
4
estt
test
4
tste
test

output
Copy

2
1
2

input
Copy

4
1
a
z
5
adhas
dasha
5
aashd
dasha
5
aahsd
dasha

output
Copy

-1
2
2
3

Note
In the first example, the moves in one of the optimal answers are:

for the first test case s=s="iredppipe", t=t="piedpiper": "iredppipe" →→ "iedppiper" →→ "piedpiper";

for the second test case s=s="estt", t=t="test": "estt" →→ "test";

for the third test case s=s="tste", t=t="test": "tste" →→ "etst" →→ "test".

 
 
문제풀이 보고서: 제목의 해석은 두 개의 길이가 n인 문자열 s와 t를 정하는 것이다. 그 중에서 s의 임의의 문자에 대해 그는 이 문자를 문자열의 첫 부분이나 끝에 놓을 수 있다. 가장 작은 조작 횟수가 얼마인지 물어보면 s=t 실현할 수 있다.
우선 명확한 것은 우리가 단일 문자를 문자열의 처음과 끝까지 조정할 수 있다는 것이다. 그러면 우리는 가장 작은 s와 t의 다른 문자를 직접 찾을 수 있다.
 
ac 코드:

#include
#include
#include
#include
using namespace std;
typedef long long ll;

int main()
{
    int t;    
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        string a,b;
        cin>>a>>b;
        int ans=1e9;
        for(int i=0;i)
        {
            int k=i;
            for(int j=0;j)
            {
                if(k;
            }//                   b，              a      
            //             ，                 /        a 
            ans=min(ans,n-k+i);
            //    cout<
        }
//        cout<sort(a.begin(),a.end());
sort(b.begin(),b.end());
//        cout<if(a!=b)
{
printf("-1");
continue;
}
printf("%d",ans);
}
}