DISPLACE  Displace
You are given two strings S1, S2 of not more than 250 characters each. S1 does not contain characters ‘(‘ and ‘)’. You can swap two consecutive characters in S1. Your task is to do it in as small a number of swapping operations as possible to obtain a string which contains S2 as a substring (you can assume that for the given input, this can always be done).
Input
The first line of the input file contains an integer t representing the number of test cases (t < 20). Then t test cases follow. Each test case has the following form:
 The first line contains S1
 The second line contains S2
Output
For each test case, output 0 iff you do not want to solve this test case. Otherwise, output a line containing the number 1 and two more lines of the following form:
 The first line contains an integer k representing the number of swap operations
 The second line contains k integers p1 p2,..., pk separated by single spaces, pi means that in the ith operation, you swapped the ith character and the (i+1)th character in S1.
Score
Your task is to minimise your score for this problem. If you choose to solve a test case and the number of swap of operations is smaller than 5000, your score is equal to the number of operations. Otherwise, your score is 5000. Your total score is equal to the sum of scores for individual tests.
Example
Input: 1 ABCDEFGH FC Output: 1 3 5 4 3 Score: 3
hide comments
(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20120701 14:58:12
there are EXACTLY 15 test cases! 

Gaurav Dhage:
20120509 18:42:54
The best solutions lists wolfram TEXT as rank 32. I don't understand.How can you submit a TEXT solution to this problem.? 

r@770r:
20110701 11:44:35
what if s1 already contain s2 as substring? 
Added by:  Duc 
Date:  20050505 
Time limit:  9s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 