APCS Jun 2024 - o078 Q3 [Python]

問題文:

K 種類の文字からなる集合と文字列 S が与えられます。この集合で作れる長さ L の文字列のうち、S の部分文字列ではないものを辞書順で最小のものから求めてください。例えば {a, c, m} で作れる長さ2の文字列は、辞書順に aa < ac < am < ca < cc < cm < ma < mc < mm です。S が accaamcm なら、含まれない最小の文字列は ma です。

def generate_strings(letters, length, current_string, all_strings):
    if length == 0:
        all_strings.append(current_string)
        return
    for letter in letters:
        generate_strings(letters, length - 1, current_string + letter, all_strings)

letters = list(input())
L = int(input())
S = input()

all_strings = []
generate_strings(letters, L, "", all_strings)

for string in all_strings:
    if string not in S:
        print(string)
        break

---

解法レポート

1. 再帰

   def generate_strings(letters, length, current_string, all_strings):
   if length == 0:
       all_strings.append(current_string)
       return
   for letter in letters:
       generate_strings(letters, length - 1, current_string + letter, all_strings)
   

   与えられた文字から指定長の全文字列を生成する再帰関数です。letters = ['a', 'b']、length = 2 とすると：

   1. 最初に generate_strings(['a', 'b'], 2, "", all_strings) を呼びます。length は0ではないのでループに入り、最初の文字 'a' を選んで generate_strings(['a', 'b'], 1, "a", all_strings) を呼びます。
   2. 2回目も length は0ではありません。再び 'a' を選び、generate_strings(['a', 'b'], 0, "aa", all_strings) を呼びます。
   3. 3回目は length が0なので、"aa" を all_strings に追加して一つ前の階層に戻ります。
   4. 2回目の呼び出しに戻り、次の文字 'b' で generate_strings(['a', 'b'], 0, "ab", all_strings) を呼びます。
   5. 4回目も length が0なので、"ab" を追加して戻ります。

   これを繰り返すと "aa"、"ab"、"ba"、"bb" が順に all_strings に追加されます。

この問題で使う知識：

• 再帰

---

• [✔️] 必要であればコードをそのまま使用できます。
• [✔️] 共有する際は出典を明記してください。
• [✔️] この記事の解法レポートはAIと共同で作成しました。誤りがあればご指摘ください。

---

実は、もっと速くできます

def generate_strings(letters, length, current_string, existing_strings):
    if length == 0:
        if current_string not in existing_strings:
            print(current_string)
            return True
        return False
    for letter in letters:
        if generate_strings(letters, length - 1, current_string + letter, existing_strings):
            return True
    return False

letters = list(input())
L = int(input())
S = input()

# 使用Set來提升查找效率
existing_strings = set(S[i:i+L] for i in range(len(S) - L + 1))

generate_strings(letters, L, "", existing_strings)

• 説明力が足りないので、あとはご自身で読み解いてください :)。

この記事は繁体字中国語の原文をAIで翻訳したものです。意味や表現に違いがある可能性があります。正確な内容は繁体字中国語の原文をご確認ください。