C++競プロ学習日記(仮)

( 学習記録であり解説Blogではないです )

No.52 よくある文字列の問題|yukicoder|深さ優先探索(DFS)

No.52 よくある文字列の問題 - yukicoder を解きました。

題意:

  • 文字列  S が与えられる。
  •  S の先頭または末尾から 1 文字取り、順に繋げて新たな文字列を作る。
  • 先頭または末尾から 1 文字取った S は、また新たな  S となり文字が無くなるまでこの操作を繰り返す。
  • 新たにできた文字列が何通りあるかを出力する。
  •  1 \leq |S| \leq 10

考察:グラフを描く

S = abc の場合のグラフを描いて考えました。

 S… 与えられた文字列
 TS の先頭、または末尾から 1 文字取って結合した新たな文字列

頂点 ST (状態)
……  S の先頭または末尾から 1 文字取り、新たな T を作る(遷移)

f:id:chiwawa_star:20170304121816j:plain

考察:実装を考える

グラフの状態である ST再帰関数の引数に持って、 S が空 ( S.empty() *1 ) になるまで、再帰的に下記 2 つの操作を繰り返します。

  •  S 先頭文字を  T に結合していく
  •  S 末尾文字を  T に結合していく

新たに出来た文字列  T は 最初に与えられる S や、組み替え次第で同じ文字列ができる事がある為、std::set *2 に入れて重複文字列をカウントしないようにします。

計算量:

  • 与えられた  S の読み込みに  \Theta(|S|) 時間
  • string::substr で  S先頭から 1 文字除いた文字列を関数に渡すのに  O(|S|) 時間。取り除いた 1 文字を  T に結合するのに  O(|S|) 時間
  • string::substr で  S末尾から 1 文字除いた文字列を関数に渡すのに  O(|S|) 時間。取り除いた 1 文字を  T に結合するのに  O(|S|) 時間
  • if 文での S.empty() 判定 1回につき  O( 1 ) 時間
  • std::set への要素挿入に  O(|S|^2) 時間
  • 解の出力に  O( 1 ) 時間
  • 全体では  O(2^{|S|}|S|^2) 時間

コード:

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
set<string> st;
void dfs( string S, string T )
{
    //基底部:Sが空になったら終わり
    if( S.empty() )
    {
        //重複を排除
        st.emplace( T );
        return;
    }
    //再帰部:
    //S[ 1 ] - S[ S.size() - 1 ]までを次に渡す, Tに「先頭」文字をくっつける
    dfs( S.substr( 1, S.size() - 1 ), T + S[ 0 ] );
    //S[ 0 ] - S[ S.size() - 1 ]までを次に渡す, Tに「末尾」文字をくっつける
    dfs( S.substr( 0, S.size() - 1 ), T + S[ S.size() - 1 ] );
}
int main()
{
    string S, T;
    cin >> S;
    
    dfs( S, T );
    
    cout << st.size() << endl;
    
    return 0;
}