AtCoder Beginner Contest 347(B – Substring)の解説 by C++

問題文

この問題はAtcoderさんのコンテストから出題されました。

B - Substring

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

今回の問題では文字列を分解して、何個部分文字列があるかを数える問題です。
例えばappという文字列の場合はa,p,ap,pp,appの五つあります。

この問題の難しいところは部分文字列の重複をカウントしないようにする点だと思います。

サンプルコード

atcoder/contest/contest347/b02.cpp at main · mintson0517/atcoder

Contribute to mintson0517/atcoder development by creating an account on GitHub.

github.com

コードの解説

string S;
    cin >> S;

    int N = S.size();
    set<string> strings; 

部分文字列を重複してカウントしないようにするにはsetを使用することをおすすめします。

    for (int i = 0; i < N; ++i) {
        for (int len = 1; len <= N - i; ++len) {
            strings.insert(S.substr(i, len));
        }
    }

Forループですべての”S.substr(何番目,どのくらいの長さ)”といった感じで部分文字列を作成して、setのデータ型に格納します。

cout << strings.size() << endl;

最後にset型のサイズ（全体の個数）を表示させて正解となります！