【AtCoder】備忘録ABC347-B

問題

PHPで解いています。
B問題はネストした繰り返し処理が肝のよう。

解答

<?php

$s = trim(fgets(STDIN)); 
$n = strlen($s); //文字数の長さを取得

$substrings = [];

//全ての部分文字列を生成し、集合に追加する
for ($i = 0; $i < $n; $i++) {
    for ($j = $i + 1; $j <= $n; $j++) {
        $sub = substr($s, $i, $j - $i); 
        $substrings[$sub] = true;
    }
}


echo count($substrings);

つまづいたポイント

重複する部分文字列を複数回数えていた。
→各部分文字列を集合（セット）に格納し、最終的にその集合の要素数を出力する

$substrings[$sub] = true;

↑これより、重複する部分文字列は集合に一度しか追加されず、最終的な集合の要素数が部分文字列の種類の数となる。
var_dumpすると、、、

$substrings = [
    "a" => true,
    "aa" => true,
    "aab" => true,
    "aaba" => true,
    "aabab" => true,
    "aababc" => true,
    "ab" => true,
    "aba" => true,
    "abab" => true,
    "ababc" => true,
    "b" => true,
    "ba" => true,
    "bab" => true,
    "babc" => true,
    "a" => true,
    "ab" => true,
    "abc" => true
];