Overview

Count the number of occurrences of the substring tanabata in each lyrics string (including overlapping occurrences), and find the song number with the highest count (if there is a tie, choose the smallest number).

Analysis

• The “summer-likeness score” we want to compute is how many times the substring tanabata appears in the string.
• An important point here is that overlapping occurrences are also counted.
  For example, in general, "aa" appears in the string "aaaa" starting at positions 0, 1, and 2, so it occurs 3 times.
  Similarly in this problem, after finding an occurrence, we need to restart the search from the next position (+1).
• Even a naive approach of “extracting a substring of length 8 from every position and checking for a match” is fast enough, since the length of tanabata is fixed at 8 and the total number of characters is at most \(10^6\) (roughly \(8 \times 10^6\) operations).
• The provided code uses Python’s str.find to count as follows:
  • Use find(pat, start) to get the first occurrence position at or after start
  • If found, increment the count and set start = pos + 1 to advance by only 1 character before searching again (handling overlaps)

Furthermore, when multiple songs have the maximum score, we choose the one with the smallest number, so: - We update only when cnt > best_score (not >=)
This ensures that in case of a tie, the song found first (= with the smaller number) is retained.

Algorithm

1. Prepare the pattern pat = "tanabata".
2. For each song \(i=1..N\), do the following:
   1. Set cnt = 0, start = 0.
   2. In a loop, execute pos = S_i.find(pat, start).
      • If pos == -1, no more occurrences are found, so exit the loop.
      • If found, do cnt += 1, and to allow overlapping, set start = pos + 1.
   3. If cnt is greater than the current maximum, update the maximum and the answer number.
3. Output the number that is retained at the end.

Complexity

• Time complexity: \(O\!\left(\sum_{i=1}^{N} |S_i|\right)\) (since the length of tanabata is a constant, each string is processed in essentially linear time)
• Space complexity: \(O(1)\) (no large additional space is used beyond the input strings)

Implementation Notes

• To count overlapping occurrences, set the next search start position to pos + 1 instead of pos + len(pat).

• To choose the smallest number in case of a tie, the update condition should be cnt > best_score (not >=).

• Since the input can be large, use sys.stdin.buffer.readline for fast reading.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N_line = input()
    if not N_line:
        return
    N = int(N_line)
    pat = "tanabata"

    best_idx = 1
    best_score = -1

    for i in range(1, N + 1):
        s = input().decode().strip()
        cnt = 0
        start = 0
        while True:
            pos = s.find(pat, start)
            if pos == -1:
                break
            cnt += 1
            start = pos + 1  # allow overlap

        if cnt > best_score:
            best_score = cnt
            best_idx = i

    sys.stdout.write(str(best_idx))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.