给出 n 个字符串,对于每个 n 个排列 p,按排列给出的顺序(p[0] , p[1] … p[n-1])依次连接这 n 个字符串都能得到一个长度为这些字符串长度之和的字符串。所以按照这个方法一共可以生成 n! 个字符串。
一个字符串的权值等于把这个字符串循环左移 i 次后得到的字符串仍和原字符串全等的数量,i 的取值为 [1 , 字符串长度]。求这些字符串最后生成的 n! 个字符串中权值为 K 的有多少个。
注:定义把一个串循环左移 1 次等价于把这个串的第一个字符移动到最后一个字符的后面。
给出 n 个字符串,对于每个 n 个排列 p,按排列给出的顺序(p[0] , p[1] … p[n-1])依次连接这 n 个字符串都能得到一个长度为这些字符串长度之和的字符串。所以按照这个方法一共可以生成 n! 个字符串。
一个字符串的权值等于把这个字符串循环左移 i 次后得到的字符串仍和原字符串全等的数量,i 的取值为 [1 , 字符串长度]。求这些字符串最后生成的 n! 个字符串中权值为 K 的有多少个。
注:定义把一个串循环左移 1 次等价于把这个串的第一个字符移动到最后一个字符的后面。
每组测试用例仅包含一组数据,每组数据第一行为两个正整数 n, K , n 的大小不超过 8 , K 不超过 200。接下来有 n 行,每行一个长度不超过 20 且仅包含大写字母的字符串。
输出一个整数代表权值为 K 的字符串数量。
3 2 AB RAAB RA
3
import java.util.ArrayList;
import java.util.Scanner;
public class JRTT4 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int n = scanner.nextInt();
int K = scanner.nextInt();
String[] strs = new String[n];
for (int i = 0; i < n; i++) {
strs[i] = scanner.next();
}
System.out.println(getNumWeightK(n, K, strs));
}
}
public static int getNumWeightK(int n, int K, String[] strs) {
int count = 0;
ArrayList<String> strings = new ArrayList<String>();
permutation(strings, strs, 0);
for (int i = 0; i < strings.size(); i++) {
int weightTemp = getWeight(strings.get(i));
if (weightTemp == K) {
count++;
}
}
return count;
}
// 循环移位得到的权重 超时
/*public static int getWeight(String s) {
int weight = 0;
char[] cs = s.toCharArray();
for (int i = 0; i < s.length(); i++) {
char temp = cs[0];
for (int j = 0; j < s.length() - 1; j++) {
cs[j] = cs[j + 1];
}
cs[s.length() - 1] = temp;
String rotateS = new String(cs);
if (rotateS.equals(s)) {
weight++;
}
}
return weight;
}*/
//求一个字符的权重
public static int getWeight(String s) {
int weight = 0;
int len = s.length();
for(int i=0;i<s.length();i++){
if(s.substring(0, i).equals(s.substring(len - i, len)) && s.substring(0, len-i).equals(s.substring(i, len))){
weight++;
}
}
return weight;
}
// 全排列
public static void permutation(ArrayList<String> strings, String[] strs, int k) {
if (k == strs.length) {
String temp = ""; //一开始用StringBuffer类来保存,就超时了。所以尽量不要用StringBuffer
for (int i = 0; i < strs.length; i++) {
temp += strs[i];
}
strings.add(temp);
}
else{
for (int i = k; i < strs.length; i++) {
swap(strs, i, k);
permutation(strings, strs, k + 1);
swap(strs, i, k);
}
}
}
public static void swap(String[] strs, int i, int j) {
if (i != j) {
String t = strs[i];
strs[i] = strs[j];
strs[j] = t;
}
}
}
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<string> strs;
vector<int> flag;
int n, k;
int count;
void backTracking(int pos, vector<int> &sequence)
{
if(pos == n)
{
string s;
for(int i = 0; i < n; i++)
s += strs[sequence[i]];
string tmps = s;
int lcount = 1;
for(int i = 0; i < s.length() / 2; i++)
{
tmps = tmps.substr(1) + tmps[0];
if(tmps == s)
{
lcount = s.length() / (i + 1);
break;
}
}
if(lcount == k)
count++;
return;
}
for(int i = 0; i < n; i++)
{
if(flag[i])
{
sequence.push_back(i);
flag[i] = false;
backTracking(pos + 1, sequence);
flag[i] = true;
sequence.resize(sequence.size() - 1);
}
}
}
int main()
{
count = 0;
cin>>n>>k;
strs.resize(n);
flag.resize(n);
vector<int> seq;
for(int i = 0; i < n; i++)
{
cin>>strs[i];
flag[i] = true;
}
backTracking(0, seq);
cout<<count<<endl;
return 0;
}
#include <iostream>
#include <vector>
#include <assert.h>
#include <cstring> // for strncmp
#include <algorithm> // for std::next_permutation
using namespace std;
bool is_eq_after_move(const string& str, const size_t offset) {
const size_t len = str.size();
if (offset == len) return true;
assert(offset >= 1 && offset < len);
// 左移 offset 位数后,与原串相等的情况之一:
// 每 offset 个数据块 都要相等
// 所以 这种情况 的字符串,长度首先必须是 offset 的 整数倍。
//
// 情况之二,串长不是 offset 的 整数倍,像这种: ABABAB , offset = 4
// 这种情况可以用递归来化解:
if (len % offset != 0) {
if (len % offset > len / 2) return false; // 加上此句可减少复杂度
return is_eq_after_move(str, len % offset);
}
// 程序能走到这的都是 之前提到的 情况一:
char* s = (char*)&str[0]; // 先指向首地址
for (size_t loop = 0, max_loop = len / offset - 1;
loop < max_loop; ++loop) {
if ( 0 != strncmp(s, s + offset, offset) ) {
return false;
}
s += offset;
}
return true;
}
void get_ret(size_t& ret, const int* pos, const size_t size,
const vector<string>& input, const size_t K) {
size_t count = 1; // 自身整体移动算一个
string newstring;
for (size_t i = 0; i < size; ++i) {
newstring += input[pos[i]];
}
const int len = newstring.size();
for (int offset = 1; offset < len; ++offset) {
// 只判断 和第一个相等的字符即可
if (newstring[offset] == newstring[0]) {
if (is_eq_after_move(newstring, offset)) {
count++;
}
}
}
if (count == K) {
ret++;
}
}
int main() {
size_t n, K;
cin >> n >> K;
vector<string> input(n);
size_t newstrlen = 0;
for (size_t i = 0; i < n; ++i) {
cin >> input[i];
newstrlen += input[i].size();
}
// 生成 0 ~ n-1 的全排列
int pos[n];
for (int i = 0; i < n; ++i) pos[i] = i;
size_t ret = 0;
do {
get_ret(ret, pos, n, input, K);
} while (std::next_permutation(pos, pos + n));
cout << ret << endl;
return 0;
}
递归生成全排列,判断权值,也就是串能分出多少个相同的子串,用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(); } }
#include<bits/stdc++.h>
using namespace std;
string s[9];
map<string,int>m;
int main(){
int n,k;cin>>n>>k;
for(int i=1;i<=n;i++)cin>>s[i];
int a[10];
for(int i=1;i<=n;i++)a[i]=i;
do{
string k;
for(int i=1;i<=n;i++)k+=s[a[i]];
m[k]++;
}while(next_permutation(a+1,a+1+n));
int ans=0;
map<string,int>::iterator it=m.begin();
for(;it!=m.end();it++){
string x=(*(it)).first;
int now=0;
for(int i=0;i<x.size();i++){//偏移量
int f=1;
for(int j=0;j<x.size();j++){
if(x[j]!=x[(j+i)%x.size()]){f=0;break;}
}
now+=f;
if(now>k)break;
}
if(now==k)ans+=m[x];
}
cout<<ans;
}
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 06 19:10:02 2016
@author: duzejie
python测试通过
基本思想:
1.生成全排列
2.减少测试次数
a.如果字符串循环左移 i 次后得到的字符串仍和原字符串全等,
则要求i是该字符串长度的因数,所以不必测试全部i
b.对于权为k的字符串,测试通过的最小i为imin= strlen / k,
所以不必测试大于imin的i
c.测试通过的i小于imin= strlen / k,可提前退出
"""
import itertools
'''测试字符串循环左移 i 次后得到的字符串是否仍和原字符串全等'''
def test(s,i):
strl = s[:i]
strr = s[i:]
newstr = strr + strl
if cmp(s,newstr)==0:
return True
lis = raw_input().split() #获取n,k
n=int(lis[0])
k=int(lis[1])
i = 0
mystring = [] #存放输入字符串列表
strlen = 0 #统计所有字符串长度
while(i<n): #从用户输入获取各个字符串,放入mystring[]
ms = raw_input()
strlen += len(ms)
mystring += [ms]
i+=1
'''mybei[]中存放所有可能的i。如果字符串循环左移 i 次后得到的字符串仍和原字符串全等,
则要求i是该字符串长度的因数'''
mybei = [x for x in range(1,strlen+1) if strlen % x == 0]
coutk = 0
newlist = range(n)
strlist = list(itertools.permutations(newlist,n)) #存放所有字符串的可能组合方式
imin = strlen / k #对于权为k的字符串,测试通过的最小i为imin
for x in strlist : #遍历所有可能组合
if strlen % k != 0:break
s = ''
for y in x:
s+= mystring[y] #生成该组合的字符串
for i in mybei: #对可能的i测试
if i > imin :break
if test(s,i):
if i < imin:
break
if i == imin:
coutk +=1
break
print(coutk)
#include <bits/stdc++.h>
using namespace std;
int getk(string &str){
int k=1;
string tmp=str;
for(int i=0;i<str.length()/2;i++){
tmp=tmp.substr(1)+tmp[0];
if(tmp==str){
k=str.length()/(i+1);
break;
}
}
return k;
}
int main(){
int n,k,p;
string str;
for(vector<string> vs;cin>>n>>k;){
vector<int> ids(n,0);
for(int i=0;i<n;ids[i]=i,++i);
for(++n;--n;cin>>str,vs.push_back(str));
do{
stringstream istr;
for(int i=0;i<ids.size();istr<<vs[ids[i++]]);
istr>>str;
if(getk(str)==k) ++n;
}while(next_permutation(ids.begin(),ids.end()));
cout<<n<<endl;
}
return 0;
}
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <functional>
#include <algorithm>
#include <stack>
#include <queue>
#include <sstream>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <random>
#include <fstream>
int main()
{
int n, K;
std::cin >> n >> K;
std::vector<std::string> orig_strs(n);
for (int i = 0; i < n; i++)
std::cin >> orig_strs[i];
std::vector<int> pa;
for (int i = 0; i < n; i++)
pa.push_back(i);
int ans = 0;
do
{
std::string str, str_bak;
for (int i = 0; i < n; i++)
str += orig_strs[pa[i]];
str_bak = str;
int k = 0;
for (int i = 1; i <= str.length(); i++)
{
std::string new_str = str.substr(i, -1) + str.substr(0, i);
if (new_str == str_bak)
k += 1;
}
if (k == K)
ans += 1;
} while (std::next_permutation(pa.begin(), pa.end()));
std::cout << ans;
return 0;
} #include <bits/stdc++.h>
using namespace std;
int main() {
int n, K, res = 0;
cin >> n >> K;
vector<string> strs(n);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
cin >> strs[i];
v[i] = i;
}
do {
string s;
for (int i : v) s += strs[i];
int n = s.size(), k = 1;
vector<int> f(n, 0);
for (int i = 1, len = 0; i < n;) {
if (s[i] == s[len]) f[i++] = ++len;
else if (len) len = f[len-1];
else f[i++] = 0;
}
if (n % (n - f[n-1]) == 0) k = n / (n - f[n-1]);
if (k == K) ++res;
} while (next_permutation(v.begin(), v.end()));
cout << res << "\n";
} def all_permutation(l, s=[]):
if len(l) == 0:
return [s + l]
else:
r = []
for i in range(len(l)):
r += all_permutation(l[0:i] + l[i + 1:], s + [l[i]])
return r
def check(s, m, k):
if m % k == 0:
for i in range(1, m):
if m % i == 0:
if s[0:i] * (m // i) == s:
break
if m // i == k:
return True
else:
return False
else:
return False
n, k = [int(ele) for ele in input().split(' ')]
r = []
while n > 0:
r.append(input())
n -= 1
r2 = all_permutation(r)
m = len(''.join(r))
ans = 0
for ele in r2:
if check(''.join(ele), m, k):
ans += 1
print(ans)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int k = scn.nextInt();
List<String> list = new ArrayList<>();
for(int i=0;i<n;i++){
list.add(scn.next());
}
List<String> all = new ArrayList<>();
backtrack(list, new ArrayList<String>(), all);
int ret = 0;
for(String str: all){
//System.out.println(str);
int c = getWeight(str);
//System.out.println(" "+c);
if(c==k)ret++;
}
System.out.println(ret);
}
public static int getWeight(String s) {
int weight = 0;
int len = s.length();
for(int i=0;i<s.length();i++){
if(s.substring(0, i).equals(s.substring(len - i, len)) && s.substring(0, len-i).equals(s.substring(i, len))){
weight++;
}
}
return weight;
}
public static void backtrack(List<String> list, List<String> tempList, List<String> all){
for(int i=0;i<list.size();i++){
String s = list.get(i);
tempList.add(s);
List<String> copy = new ArrayList<>(list);
copy.remove(i);
backtrack(copy, tempList, all);
tempList.remove(tempList.size()-1);
}
if(list.size()==0){
StringBuilder sb = new StringBuilder();
for(String str: tempList){
sb.append(str);
}
all.add(sb.toString());
}
}
}
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> get_allstr(vector<string> input)
{
int n=input.size();
int index[n];
for(int i=0;i<n;i++)
index[i]=i;
vector<string> allstr;
do
{
string newstr;
for(int i=0;i<n;i++)
newstr+=input[index[i]];
allstr.push_back(newstr);
}while(next_permutation(index,index+n));
return allstr;
}
int get_k(string str)
{
int k=0;
string str_left_move=str;
for(int i=1;i<=str.size();i++)
{
str_left_move=str_left_move.substr(1)+str_left_move[0];
if(str==str_left_move)
k++;
}
return k;
}
int main()
{
int n,K;cin>>n>>K;
vector<string> input(n);
for(int i=0;i<n;i++)
cin>>input[i];
vector<string> allstr=get_allstr(input);
int count=0;
for(int i=0;i<allstr.size();i++)
{
int k=get_k(allstr[i]);
if(k==K)
count++;
}
cout<<count<<endl;
return 0;
}
importjava.util.ArrayList;importjava.util.Scanner;publicclassMain {staticArrayList<String> list =newArrayList<>();publicstaticvoidmain(String[] args) {Scanner scan =newScanner(System.in);while(scan.hasNext()){intn = scan.nextInt();//<=8intk = scan.nextInt();//<=200,权值String[] strs =newString[n];for(inti=0;i<n;i++){strs[i] = scan.next();//size<=20}perm(strs,0, strs.length);intcount =0;//权值为K的字符串数量for(inti=0;i<list.size();i++){if(getK(list.get(i))==k){count++;}}System.out.println(count);list.clear();}}//获取权值privatestaticintgetK(String s){String news = s+s;intcount =0;for(inti=1;i<=s.length();i++){if(news.substring(i, i+s.length()).equals(s)){count++;}}returncount;}privatestaticvoidperm(String[] strs,intstart,intend){String s ="";if(start==end){//一个字符串全排列for(inti=0;i<strs.length;i++){s+=strs[i];}list.add(s);}else{//多个字符串全排列for(inti=start;i<end;i++){String str = strs[start];strs[start] = strs[i];strs[i] = str;perm(strs,start+1,end);strs[i] = strs[start];strs[start] = str;}}}}
// 复杂度太高了?没过。。不过应该是对的
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;
}
}
// 首先对问题进行划分
// 两个基本模块:生成全排列,字符串权重计算
// 生成全排列:递归
// 字符串权重:等价于寻找最小循环子串
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int n, K;
int count = 0;
// 计算字符串权重
void isKWeight(vector<string> strs, vector<int> &vi) {
string s;
for (int i = 0; i < vi.size(); ++i) s += strs[vi[i]];
string tmps(s);
int lc = 1;
// 计算字符串权重等价于寻找最小循环字符串
for (int i = 0; i < s.size() / 2; ++i) {
tmps = tmps.substr(1) + tmps[0];
if (tmps == s) {
// 根据最小循环字符串计算权重
lc = s.size() / (i + 1);
break;
}
}
if (lc == K) ++count;
}
// 生成全排列
void permutations(vector<string> strs, vector<int> &vi, int start, int end) {
if (start == end) {
isKWeight(strs, vi);
} else {
for (int i = start; i <= end; ++i) {
// 交换元素,使每一个元素都有放在第一位的机会
swap(vi[start], vi[i]);
// 递归调用
permutations(vi, start + 1, end);
// 恢复原始的list,不影响下次递归调用
swap(vi[start], vi[i]);
}
}
}
int main() {
cin >> n >> K;
count = 0;
vector<string> ss(n);
vector<int> vi(n);
for (int i = 0; i < n; ++i) {
cin >> ss[i];
vi[i] = i;
}
permutations(ss, vi, 0, n - 1);
cout << count << endl;
}
//java写的,思路参考上面的,把算移位权重 直接用字符串切分比较,算是优化了,就没有超时,AC了 import java.util.*; public class Main { static List<String> list = new ArrayList<String>(); public static void main(String[] args) { // TODO Auto-generated method stub Scanner scan = new Scanner(System.in); while(scan.hasNext()){ int n = scan.nextInt(); int k = scan.nextInt(); String[] strs = new String[n]; int count = 0; for(int i=0; i<n; i++){ strs[i] = scan.next(); } arrange(strs, 0, n); for(int i=0; i<list.size(); i++){ if(weight(list.get(i)) == k) count ++; } System.out.println(count); } } public static void arrange(String[] arr, int start, int len){ if(start == len - 1){ String temp = ""; for(int i=0; i<arr.length; i++) temp += arr[i]; list.add(temp); }else { for(int i=start; i<len; i++){ swap(arr,start,i); arrange(arr,start + 1, len); swap(arr,start,i); } } } public static void swap(String[] arr, int x, int y){ String temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; } public static int weight(String str){ int ans = 0; int len = str.length(); for(int i=1; i<=str.length(); i++){ if(str.substring(0,i).equals(str.substring(len-i,len)) && str.substring(0,len-i).equals(str.substring(i,len))) ans ++; } return ans; } }