AtCoder ABC 347 B - Substring (6Q, 灰色, 200 点)

set の使い方を覚えよう！

• 問題へのリンク

問題概要

文字列 が与えられる。

の連続する部分文字列として考えられるものの個数を求めよ。

制約

• 

考えたこと

の連続する部分文字列をすべて取り出して、それを set に格納して、そのサイズを求めれば良い。

の連続する部分文字列は次のようにして取り出して、set に格納できる。

// 文字列 S の区間 [i, j) を取り出す
set<string> se;
for (int i = 0; i < S.size(); i++) {
    for (int j = i+1; j <= S.size(); j++) {
        string sub = S.substr(i, j - i);
        se.insert(sub);
    }
}

最後に、集合のサイズを答えれば良い。

コード

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

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