Yukicoder052 よくある文字列の問題

問題概要

文字列$S$が与えられる。 文字列$S$の「先頭」または「末尾」から1文字ずつ文字をとってきて、 取った文字列とは別に、取った文字を順番につなげて新たに文字列を作る。 $S$は、文字を取った後の文字列を新たな$S$として$S$の文字列がなくなるまで繰り返す。

この時、新たにできる文字列は何通りの文字列ができるか？

$|S|\leqq10$

yukicoder052

解法

愚直に全探索する。

計算量:$O(2^{|S|}})$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    #define SZ(a) int((a).size())
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    void search(string s, set<string>& se, string res = "") {
        if (SZ(s) == 0) {
            se.insert(res);
            return;
        }
        search(s.substr(1, SZ(s) - 1), se, res + s.front());
        search(s.substr(0, SZ(s) - 1), se, res + s.back());
    }
    
    LL N;
    LL ans = 0LL;
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        string s; cin >> s;
    
        set<string> se;
        search(s, se);
        ans = SZ(se);
        cout << ans << "\n";
    
    
        return 0;
    }