問題
http://community.topcoder.com/stat?c=problem_statement&pm=10195&rd=13695
解き方
ある文字列がずらすことで何通り同じ文字列が現れるかは、
その文字列で割りきれるサブ文字列がいくつつながっているかでわかる。
例えば長さ１２の文字列中、長さ３のサブ文字列が４つ連なっている場合、
１２／３で４通り存在する。
上記のように判定することで計算量がO(８！×１６０×sqrt(160)）で
時間内に収めることができる。
コード
class MagicWords {
public:
int calc(string str){
int n=str.size();
for(int i=1;i<n;i++)if(n%i==0){
int valid=1;
for(int j=0;j<n;j++)if(str[j]!=str[(j+i)%n])valid=0;
if(valid)return n/i;
}
return 1;
}
int count(vector<string> S, int K) {
int m=S.size();
vector<int> idx(m);
FORE(i,0,m)idx[i]=i;
sort(all(idx));
int ret=0;
do{
string str="";
FORE(i,0,m)str+=S[idx[i]];
if(calc(str)==K)ret++;
}while(next_permutation(all(idx)));
return ret;
}
};
public:
int calc(string str){
int n=str.size();
for(int i=1;i<n;i++)if(n%i==0){
int valid=1;
for(int j=0;j<n;j++)if(str[j]!=str[(j+i)%n])valid=0;
if(valid)return n/i;
}
return 1;
}
int count(vector<string> S, int K) {
int m=S.size();
vector<int> idx(m);
FORE(i,0,m)idx[i]=i;
sort(all(idx));
int ret=0;
do{
string str="";
FORE(i,0,m)str+=S[idx[i]];
if(calc(str)==K)ret++;
}while(next_permutation(all(idx)));
return ret;
}
};