[codechef] Magical Transformation(dp, 테크닉 문제)

Irfan and his brother Yusuf were looking at photographs of their vacation to Hawaii. Irfan noticed something interesting. He noticed that if their aunt Mansi had a big beard and a moustache she would resemble their uncle Amit. He tried to modify the people in other photographs in such a way so that they would resemble someone else. Yusuf who was into programming decided to do something similar with strings. He wrote down 2 words and tried to transform one word into another.
He decided that the operations that maybe performed on the strings could be: Inserting a character at any position, removing an existing character, modifying an existing character and swapping 2 adjacent characters. Each operation is counted as one move. While doing this he noticed that there is more than one way to complete this transformation. He wants your help to write a program that can find out the minimum number of moves required transform a given word into another given word.

Input

The first line contains a single integer T , the number of test cases. T test cases follow.
The only line of each test case contains 2 strings (contains only lower case letters), separated by a single space.

Output

For each test case, output a single line containing an integer which denotes the minimum number of moves required transform a given word into another given word.

Constraints

1 ≤ T ≤ 1000
1 ≤ |S| ≤ 100
 

Example

Input:
1
smatr smart

Output:
1

http://www.codechef.com/problems/MOUSCH01
Inserting a character at any position, removing an existing character, modifying an existing character and swapping 2 adjacent characters
한 문자열을 다른 문자열로 바꾸는 데 필요한 최소 작업 수를 물어보십시오.
dp[i][j]는 A의 전 i위 B의 전 j위를 찾을 때 필요한 최소 조작수를 나타낸다.핵심 코드는 다음과 같습니다.
dp[i][j]=min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1])+1은 먼저 세 가지 조작을 고려한다.dp[i-1][j-1]은 j의 위치를 수정하는 값이고, dp[i-1][j]는 ij의 경우 j의 끝에 값을 삽입한다.다음 코드는 swap을 고려합니다.인접한 것이기 때문에last수 그룹은 문자열에서 알파벳이 마지막으로 나타난 위치를 기록하고 그 중 한 쪽이 교환할 두 알파벳이 인접한 위치에 있는지 관찰한다.예를 들어 12345와 15234의 경우 현재의 두 끝은 4와 5로 각각 다른 문자열에서 4와 5가 마지막으로 나타난 위치를 찾는다. 5->2, 5->4는 A에서 4와 5가 나타난 위치가 서로 인접하기 때문에 우리는 4와 5(+1)를 교환하고 dp[3][1]의 상태를 더하여 5의 뒤에 2와 3을 삽입하면 된다.

#include<iostream>  
#include<algorithm>  
#include<string>  
#include<map>  
#include<vector>  
#include<cmath>  
#include<string.h>  
#include<stdlib.h>  
#include<cstdio>  
#define ll long long  
using namespace std;  
int dp[101][101];
int last1[28],last2[28];
int main(){
	int t;
	cin>>t;
	while(t--){
		char x[105],y[105];
		cin>>x>>y;
		int len1=strlen(x),len2=strlen(y);
		for(int i=len1;i>=1;--i)
			x[i]=x[i-1];
		for(int i=len2;i>=1;--i)
			y[i]=y[i-1];
		for(int i=0;i<=len1;++i)
			dp[i][0]=i;
		for(int i=1;i<=len2;++i)
			dp[0][i]=i;
		memset(last1,-1,sizeof(last1));
		for(int i=1;i<=len1;++i){
			memset(last2,-1,sizeof(last2));
			for(int j=1;j<=len2;++j){
				if(x[i]==y[j])
					dp[i][j]=dp[i-1][j-1];
				else{
					dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
					if(last1[y[j]-'a']>0&&last2[x[i]-'a']>0){
						if(last1[y[j]-'a']==i-1)  //         [swapping 2 adjacent characters]
							dp[i][j]=min(dp[i][j],dp[last1[y[j]-'a']-1][last2[x[i]-'a']-1]+j-last2[x[i]-'a']-1+1);
						else if(last2[x[i]-'a']==j-1)
							dp[i][j]=min(dp[i][j],dp[last1[y[j]-'a']-1][last2[x[i]-'a']-1]+i-last1[y[j]-'a']-1+1);
					}
				}
				last2[y[j]-'a']=j;
			}
			last1[x[i]-'a']=i;
		}
		cout<<dp[len1][len2]<<endl;
	}
	return 0;
}