DescriptionYouaregivenastringAandastringBofthesamelength,lessthan1000.InoneturnyoucanselectanycharacterofAandmoveittothebeginningofthestring(i.e.,beforethefirstcharacterofA).Outputtheminimalnumberofturnsne

Question

Description
You are given a string A and a string B of the same length,less than 1000.
In one turn you can select any character of A and move it to the beginning of the string (i.e.,
before the first character of A).
Output the minimal number of turns needed to transform A into B.If it's impossible,output -1
instead.
Input
The first line of input contains an integer T,indicates the cases.
Next T lines each contains 2 strings A and B that contain only lowercase letters
Output
Output T lines each contains the answer required.
Sample Input
3
abc cba
a b
aaabbb bbbaaa
Sample Output
2
-1
3

Answer 1

题目等价于在A中找出一个最长的与B后缀相同的子序列.

#include 
#include 
#include 
using namespace std;

int main(){
\x09int i, j, n, T;
\x09cin >> T;
\x09while(T--){
\x09\x09string A, B;
\x09\x09cin >> A >> B;
\x09\x09n = A.length();

\x09\x09vector vA(26), vB(26);
\x09\x09for(i=0; i\x09\x09\x09vA[A[i]-'a']++, vB[B[i]-'a']++;

\x09\x09for(i=n-1, j=n-1; i>=0; i--)
\x09\x09\x09j -= (A[i] == B[j]);
\x09\x09cout << ((vA==vB)? j+1: -1) << endl;
\x09}
}