gotutiyan’s blog

競技プログラミングをやったりopenframeworksでお絵かきをしたりしています。

AOJ 列車の編成パート(Organize Your Train part II) 解説

問題
Organize Your Train part II | Aizu Online Judge


解説
文字列を2分割した後は以下の操作ができます。以下、分割した後の2つの文字列をA,Bとおきます。

・A,Bはそれぞれ反転できる。
・文字列を AB 、またはBA のどちらの順でも連結できる。

これ以外にできる操作はありません。
また、文字列の重複による2重カウントを除くために、集合のsetを使います。setは自由に要素を追加できますが、既に存在する要素を追加しようとしたときは追加されません。
生成された文字列を全てsetに入れた後、setに格納された要素数を見ればそれが答えになります。

また、A,Bを反転するしないかは、反転するを1、反転しないを0とすれば00, 01,10,11の4通りです。これはforで全探索します。

int main(){
    int n;
    cin>>n;
    rep(i,0,n){
        set<string> st;
        string s;
        cin>>s;
        string ls,rs;
        rep(i,0,s.length()){
            ls=s.substr(0,i);
            rs=s.substr(i,s.length()-i);
            rep(j,0,2){
                rep(k,0,2){
                    st.insert(ls+rs);
                    st.insert(rs+ls);
                    reverse(all(ls));
                     
                }
                reverse(all(rs));
            }
        }
         
        cout<<st.size()<<endl;
    }
     
    return 0;
}