ABC-032-B 高橋君とパスワード

■■■問題■■■

高橋君の会社には、秘密の金庫があります。
この金庫にはパスワードをかけているのですが、高橋君はそのパスワードを忘れてしまいました。
しかし、幸運なことに、手元にはパスワードのヒントが以下のように書かれていました。

●パスワードは、この紙に書かれている文字列sの長さkの部分文字列(※)のどれかである。

高橋君は、ありうるパスワードを全部試せば金庫を開けられる！と喜びました。
しかし、文字列sはとても長い可能性があるし、
しかも同じ部分文字列が複数個文字列s中に存在する可能性もあります。
明らかに、重複したパスワードを繰り返し試す必要はありません。

そこで、手動で全てのパスワードを試す前に、
試す必要がある異なるパスワードの数がいくつあるかを数えることにしました。

あなたの仕事は、文字列sの内容が与えられるので、
試す必要がある異なるパスワードの数がいくつあるかを高橋君に教えてあげることです。

(※)文字列sの「部分文字列」とは、文字列sに含まれるある区間を取り出した文字列のことです。
例えば、abcの部分文字列としてa,b,c,ab,bc,abcなどが挙げられます。
acやbaなどは部分文字列ではないことに注意してください。

■■■入力■■■

s
k

●1行目には、ヒントの紙に書かれている文字列s (1 <= |s| <= 300) が与えられる。
  sは英小文字(a-z)のみから成る。|s| は文字列sの長さを表す。
●2行目には、パスワードとしてありうる整数k (1 <= k <= 300) が与えられる。
  kは |s| よりも大きいことがある。

■■■出力■■■

出力は以下の形式で標準出力に行うこと。
1行目に、パスワードとして考えられる文字列の数を出力せよ。末尾の改行を忘れないこと。

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("abcabc");
            WillReturn.Add("2");
            //3
            //パスワードとしてありうる部分文字列の集合は、{ab,bc,ca}です。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("aaaaa");
            WillReturn.Add("1");
            //1
            //パスワードとしてありえる部分文字列は、aのみです。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("hello");
            WillReturn.Add("10");
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string s = InputList[0];
        int k = int.Parse(InputList[1]);

        var KouhoSet = new HashSet<string>();
        int UB = s.Length - 1;
        for (int I = 0; I <= UB; I++) {
            if (I + k - 1 > UB) continue;
            KouhoSet.Add(s.Substring(I, k));
        }
        Console.WriteLine(KouhoSet.Count);
    }
}

解説

HashSetで重複を排除してます。