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

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

題意：

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

考察：グラフを描く

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

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

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

考察：実装を考える

グラフの状態である $S$ と $T$ を再帰関数の引数に持って、 $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;
}