Overview

Given the lyrics of each song, determine the number of occurrences of the substring tanabata (= summer-likeness score) and output the number of the song with the highest score.

Analysis

In this problem, we need to count how many times the substring tanabata appears in each string \(S_i\). For example, in a string like tanabatatana, tanabata appears once starting from the beginning, and there may also be a tanabata starting from the second character, so we need to count with overlaps allowed.

A naive approach would be to check substrings one by one using brute force, but since the string length can be up to \(10^5\), searching each time in \(O(|S_i|)\) could require up to \(O(10^{10})\) total computation in the worst case, which may not finish in time.

However, by using Python’s standard library function str.find(), we can efficiently search for substring positions. This function searches from the beginning and returns the position where the match is found, or -1 if not found. Additionally, since we can specify a starting position, we can count overlapping substrings without missing any.

Using this method, we can count in linear time for each string, and the overall execution is sufficiently fast.

Algorithm

1. Define a function count_tanabata(s) that counts the number of occurrences of the substring tanabata in each string \(S_i\).
   • Use s.find('tanabata', start) to find the first position of tanabata at or after start.
   • If found, increment the count and resume from pos + 1 (to allow overlaps).
   • End the loop when no more occurrences are found.
2. Compute the score for each song while updating the maximum score and its index.
3. Finally, output the smallest index among those with the maximum score.

Complexity

• Time complexity: \(O\left(\sum_{i=1}^{N} |S_i|\right)\)
  • Since each string is scanned only once, the computation is proportional to the total number of characters.
• Space complexity: \(O(1)\)
  • No additional large data structures are used; processing is possible with constant memory.

Implementation Notes

• By passing the starting position as the second argument to the find() function, overlapping substrings can be correctly counted.

• When scores are tied, the smaller index should be prioritized, so the update should only occur when if score > max_score: (i.e., strictly greater).

• Since input strings may contain newlines or other whitespace, it is safe to use strip() to remove extraneous whitespace.

  Source Code

def count_tanabata(s):
    count = 0
    start = 0
    while True:
        pos = s.find('tanabata', start)
        if pos == -1:
            break
        count += 1
        start = pos + 1
    return count

N = int(input())
max_score = -1
result_index = -1

for i in range(N):
    S = input().strip()
    score = count_tanabata(S)
    if score > max_score:
        max_score = score
        result_index = i + 1

print(result_index)

This editorial was generated by qwen3-coder-480b.