【AtCoder】ABC 347 B - Substring | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 81

問題概要

英小文字からなる文字列 が与えられる。 の連続部分文字列のうち、空でないものは何種類あるか。

制約

• の長さは1以上100以下。

考察

C++ のsubstr(pos, n)は、pos番目からn文字の連続部分文字列を返す。ただし、nは省略出来て、その場合はpos番目から文字列の最後 (string::npos) までの連続部分文字列を返す。なお、 C++20 までは、nのデフォルト値はstring::nposである。

本問ではこれを使うことによって の連続部分文字列を列挙していく。具体的には、 の長さを として、posを0からlまで、nを1からlまでループさせればよい。これで正しく動作する理由は、この関数の戻り値の項を参照。

あとは列挙した各要素をsetに格納して、最終的なsetの長さを出力すればよい。

コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (ll i = (start); i < (ll)(end); i++)

// ======================================== //

int main()
{
    string S;
    cin >> S;

    set<string> st;
    rep(i, 0, S.size())
    {
        for (int j = 1; i + j <= S.size(); j++)
        {
            st.insert(S.substr(i, j));
        }
    }
    cout << st.size() << endl;
}

atcoder.jp

実装時間: 5分