ABC347 B問題（Substring）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）347 のB問題をC++とPythonで解いてみました。ABC347は、2024年3月30日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

B問題 Substring（Difficulty : 81）

問題はリンク先をご覧ください。

ABC347 B問題 Substring

すべての部分文字列の個数を求めます。AtCoder Problems による Difficulty は 81 でした。

解答案

C++ プログラム例（ABC347B）

string クラスが持つメソッド substr で部分文字列を切り取ります。substr の第2引数は長さになります。[left, right) を切り出す場合、substr(left, right – left) を指定します。

以下が、C＋＋プログラムとなります。

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

int main()
{
	string s;
	cin >> s;
	int n = s.length();

	set<string> result;
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			result.insert(s.substr(i, j - i));
		}
	}

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

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC347B）

部分文字列の取り出しは、Python のスライス記法に合わせていましたので、スッキリと書けています。以下となります。

"""AtCoder Beginner Contest 347 B"""
s = input()
n = len(s)

result = set()
for i in range(n):
    for j in range(i + 1, n + 1):
        result.add(s[i:j])

print(len(result))

こちらも「AC」と判定されました。

最後に

C++ の substr と、Python のスライス記法で指定するものが異なります。個人的には、Python のスライス記法の方が分かりやすく感じます。

引き続き ABC の問題を紹介していきます。