DISPLACE - Displace

no tags 

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).


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


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 i-th operation, you swapped the i-th character and the (i+1)-th character in S1.


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.



5 4 3


hide comments
(Tjandra Satria Gunawan)(曾毅昆): 2012-07-01 14:58:12

there are EXACTLY 15 test cases!

Gaurav Dhage: 2012-05-09 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: 2011-07-01 11:44:35

what if s1 already contain s2 as substring?

Added by:Duc
Time limit:9s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET