魔法权值

// 复杂度太高了？没过。。不过应该是对的
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * Created by Gdeer on 2016-9-8.
 */
public class Main3 {

    private static ArrayList<String> list = new ArrayList<>();
    private static ArrayList<Integer> resultList = new ArrayList<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n,k;

        while (scanner.hasNext()){
            list = new ArrayList<>();
            resultList = new ArrayList<>();
            n = scanner.nextInt();
            k = scanner.nextInt();

            for (int i = 0; i < n; i++) {
                String str = scanner.next();
                list.add(str);
            }

            int[] indexs = new int[list.size()];
            for (int i = 0; i < indexs.length; i++) {
                indexs[i] = i;
            }
            arrange(indexs, 0);

            int m = 0;
            for (int i : resultList) {
                if (i == k){
                    m++;
                }
            }
            System.out.println(m);
        }
    }

    private static void arrange(int[] array, int a) {
        int n = array.length;
        if (a == n - 1) {
            String s = createStr(array, list);
            resultList.add(getCount(s));
        } else {
            for (int i = 0; i < n - a; i++) {
                swap(array, a, a + i);
                arrange(array, a + 1);
                swap(array, a, a + i);
            }
        }
    }

    private static String createStr(int[] array, List list) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < array.length; i++) {
            sb.append(list.get(array[i]));
        }
        return sb.toString();
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private static int getCount(String str) {
        int count = 1;
        for (int i = 0; i < str.length(); i++) {
            StringBuilder sb = new StringBuilder();
            String subStr = str.substring(0, i + 1);
            for (int j = 0; j < str.length() / subStr.length(); j++) {
                sb.append(subStr);
            }
            if (sb.toString().equals(str)) {
                count = str.length() / subStr.length();
                break;
            }
        }
        return count;
    }
}

	递归生成全排列，判断权值，也就是串能分出多少个相同的子串，用KMP可解，



	判断n-next[n]能否整除n，可以知道串是否由多个相同字串组成,



	除完的商就是权值，不能整除的串权值为1.



	
	

		import java.util.*;
public class Main{
	static ArrayList<String> res;
    public static int next(String arr){
    	int[] next=new int[arr.length()+1];
    	int res=1;
    	next[0]=next[1]=0;
    	int j=0;
    	for(int i=1;i<arr.length();i++){
    		while(j>0&&arr.charAt(i)!=arr.charAt(j)) j=next[j];
    		if(arr.charAt(i)==arr.charAt(j)) {
    			j++;
    		}
    		next[i+1]=j;
    	}
    	if(arr.length()%(arr.length()-next[arr.length()])==0)
    		res=arr.length()/(arr.length()-next[arr.length()]);
    	return res;
    }
    public static void allString(String[] strr,int s,int n){
    	String tmp;
    	if(s==(n-1)){
    		tmp="";
    		for(int i=0;i<n;i++){
    			tmp+=strr[i];
    		}
    		res.add(tmp);
    	}  
    	for(int i=s;i<n;i++){
    		tmp=strr[s];
    		strr[s]=strr[i];
    		strr[i]=tmp;
    		allString(strr,s+1,n);
    		tmp=strr[s];
    		strr[s]=strr[i];
    		strr[i]=tmp;
    	}
    }
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n,k,count;
		String[] strr;
		while(sc.hasNext()){
			res=new ArrayList<String>();
			count=0;
			n=sc.nextInt();
			k=sc.nextInt();
			strr=new String[n];
			for(int i=0;i<n;i++){
				strr[i]=sc.next();
			}
			allString(strr,0,n);
			for(int i=0;i<res.size();i++){
				if(next(res.get(i))==k)
					count++;
			}
			System.out.println(count);
		}
		sc.close();
	}
}