概要

\(N\) 曲の歌詞それぞれについて、部分文字列 tanabata の出現回数（夏らしさスコア）を数え、スコアが最大の曲番号を求める問題です。

考察

素朴なアプローチとその問題点

Pythonの str.count() メソッドを使えば簡単に部分文字列の出現回数を数えられます。

score = s.count("tanabata")

実は、この問題では str.count() でも十分高速に動作します。しかし、一般的な部分文字列検索の問題では、検索パターンによっては最悪計算量が \(O(nm)\)（\(n\): テキスト長、\(m\): パターン長）となる可能性があります。

より確実なアプローチ

文字列検索の効率的なアルゴリズムとして KMP法（Knuth-Morris-Pratt algorithm） を使用することで、確実に \(O(n + m)\) の計算量で検索できます。

KMP法の基本的な考え方

KMP法の核心は「検索に失敗したとき、どこまで戻ればよいか」を事前に計算しておくことです。

例えば、パターン tanabata でテキストを検索中に失敗した場合： - 「tanab まで一致したが次で失敗」→ パターン内で ta が重複しているので、2文字分の一致を活かして検索を続けられる

この「どこまで戻るか」の情報を 失敗関数（failure function） として事前計算します。

アルゴリズム

1. 失敗関数の構築

パターン tanabata に対して、各位置 \(i\) について「パターンの先頭から \(i\) 文字目までの部分で、接頭辞と接尾辞が一致する最大長」を計算します。

位置	0	1	2	3	4	5	6	7
文字	t	a	n	a	b	a	t	a
失敗関数	0	0	0	0	0	0	1	2

例えば位置7では、tanabata の先頭の ta と末尾の ta が一致するので値は2です。

2. パターン検索

テキストを1文字ずつ走査し、パターンと比較します。 - 一致した場合：パターンの次の位置へ進む - 不一致の場合：失敗関数を使って「戻り先」を決定し、無駄な比較をスキップ - パターン全体が一致したら：カウントを増やし、失敗関数を使って次の検索開始位置を決定

3. 最大スコアの曲を特定

各曲のスコアを計算しながら、最大スコアとその曲番号を更新していきます。同スコアの場合は先に見つかった（番号が小さい）ものを保持します。

計算量

• 時間計算量: \(O(\sum_{i=1}^{N} |S_i| + N \cdot m)\)
  • 各歌詞 \(S_i\) に対して \(O(|S_i| + m)\) で検索（\(m = 8\) は tanabata の長さ）
  • 全体では \(O(\sum |S_i|)\) となり、制約より \(O(10^6)\)
• 空間計算量: \(O(m)\)
  • 失敗関数の配列に \(O(m)\)（\(m = 8\) なので定数）
  • 入力文字列は1曲ずつ処理するため、同時に保持する必要があるのは1曲分のみ

実装のポイント

1. 曲番号は1-indexed: 問題文では曲番号が1から始まるため、ループを range(1, N+1) で回すと管理しやすい

2. 初期値の設定: max_score = -1 として初期化することで、スコア0の曲しかない場合でも正しく最初の曲が選ばれる

3. 失敗関数の重複利用: パターン tanabata は固定なので、本来は失敗関数を一度だけ計算して使い回すべきですが、\(m = 8\) と小さいため毎回計算しても問題ない

4. 重複するマッチの処理: tanabata 同士は重複しないが、一般的なKMP法では j = failure[j-1] によって重複するマッチも正しくカウントできる（例：パターン aa でテキスト aaa を検索すると2回マッチ）

   ソースコード

def count_tanabata(s):
    """Count occurrences of 'tanabata' in string s using KMP algorithm"""
    pattern = "tanabata"
    m = len(pattern)
    n = len(s)
    
    if n < m:
        return 0
    
    # Build failure function for KMP
    failure = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = failure[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        failure[i] = j
    
    # Search for pattern in s
    count = 0
    j = 0
    for i in range(n):
        while j > 0 and s[i] != pattern[j]:
            j = failure[j - 1]
        if s[i] == pattern[j]:
            j += 1
        if j == m:
            count += 1
            j = failure[j - 1]
    
    return count


def main():
    N = int(input())
    max_score = -1
    best_song = 1
    
    for i in range(1, N + 1):
        s = input()
        score = count_tanabata(s)
        if score > max_score:
            max_score = score
            best_song = i
    
    print(best_song)


if __name__ == "__main__":
    main()

---

この解説は claude4.5opus によって生成されました。