TopCoder SRM 398 Level2 900
http://www.topcoder.com/stat?c=problem_statement&pm=8160
一組字符串，如何將其中一部分右移若干格，使得某一列的縱向恰好為要求的字符串，并且給出移動最少的答案。

這一題乍一看覺得很復雜
有點像之前做過的吉他琴弦的那一題
可是這個復雜度2^50是吃不消的
但是這里有兩點不同
一個是這里只能右移
另一個很重要的是這個某一列將成為一個有參考意義的坐標
即用這個列號來遍歷 看答案在哪一列解答最少
想通這一點 后面就很容易了
 1import java.util.*;
 2import java.util.regex.*;
 3import java.text.*;
 4import java.math.*;
 5import java.awt.geom.*;
 6
 7public class MatchString
 8{
 9    public int placeWords(String matchString, String[] matchWords)
10    {
11        List<ArrayList<Integer> > occur = new ArrayList<ArrayList<Integer> >();
12        int L = matchWords.length;
13        int end = 0;
14        int start = Integer.MAX_VALUE;
15        int i,j;
16        for(i = 0 ; i < L ; ++ i){
17            ArrayList<Integer> temp = new ArrayList<Integer>();
18            char c = matchString.charAt(i);
19            for(j = 0 ; j < matchWords[i].length(); ++ j){
20                if(matchWords[i].charAt(j) == c)
21                    temp.add(j);
22            }
23            if(temp.isEmpty()) return -1;
24            occur.add(temp);
25            if(matchWords[i].length() > end)
26                end = matchWords[i].length();
27            if(temp.get(0) < start)
28                start = temp.get(0);
29        }
30        int ans = Integer.MAX_VALUE;
31        Outer:
32        for(i = start; i <= end; ++ i){
33            int tempans = 0;
34            for(int k = 0 ; k < L; ++ k){
35                j = 0;
36                while(j < occur.get(k).size() && occur.get(k).get(j) <= i)
37                    ++j;
38                if(j == 0)
39                    continue Outer;
40                tempans += i - occur.get(k).get(j-1);                
41            }
42            ans = Math.min(ans, tempans);
43        }
44        return ans;
45    }
46}