Overview

For each of the \(N\) song lyrics, count the number of occurrences of the substring tanabata (the summer-like score), and find the song number with the maximum score.

Analysis

Naive Approach and Its Issues

Using Python’s str.count() method, we can easily count the occurrences of a substring.

score = s.count("tanabata")

In fact, for this problem, str.count() works efficiently enough. However, in general substring search problems, depending on the search pattern, the worst-case time complexity can be \(O(nm)\) (\(n\): text length, \(m\): pattern length).

A More Reliable Approach

By using the KMP algorithm (Knuth-Morris-Pratt algorithm), an efficient string searching algorithm, we can guarantee a search with \(O(n + m)\) time complexity.

Basic Idea of KMP Algorithm

The core of the KMP algorithm is to precompute “how far back to go when a search fails.”

For example, when searching text with the pattern tanabata and a failure occurs: - “Matched up to tanab but failed at the next character” → Since ta appears twice in the pattern, we can continue the search by utilizing the 2-character match

This information about “how far to go back” is precomputed as the failure function.

Algorithm

1. Building the Failure Function

For the pattern tanabata, we compute for each position \(i\) “the maximum length where a prefix matches a suffix within the substring from the beginning to the \(i\)-th character of the pattern.”

Position	0	1	2	3	4	5	6	7
Character	t	a	n	a	b	a	t	a
Failure Function	0	0	0	0	0	0	1	2

For example, at position 7, the ta at the beginning of tanabata matches the ta at the end, so the value is 2.

2. Pattern Search

Scan the text character by character and compare with the pattern. - If matched: Move to the next position in the pattern - If mismatched: Use the failure function to determine the “fallback position” and skip unnecessary comparisons - If the entire pattern is matched: Increment the count and use the failure function to determine the next search starting position

3. Identify the Song with Maximum Score

While calculating each song’s score, update the maximum score and its song number. In case of a tie, keep the one found first (with the smaller number).

Time Complexity

• Time complexity: \(O(\sum_{i=1}^{N} |S_i| + N \cdot m)\)
  • For each lyrics \(S_i\), search takes \(O(|S_i| + m)\) (\(m = 8\) is the length of tanabata)
  • Overall, this becomes \(O(\sum |S_i|)\), which is \(O(10^6)\) according to the constraints
• Space complexity: \(O(m)\)
  • \(O(m)\) for the failure function array (\(m = 8\), so it’s constant)
  • Since input strings are processed one song at a time, we only need to hold one song at a time

Implementation Notes

1. Song numbers are 1-indexed: Since song numbers start from 1 in the problem statement, using range(1, N+1) for the loop makes management easier

2. Initial value setting: By initializing with max_score = -1, even when all songs have a score of 0, the first song is correctly selected

3. Reusing the failure function: Since the pattern tanabata is fixed, ideally the failure function should be computed once and reused, but since \(m = 8\) is small, computing it each time is not a problem

4. Handling overlapping matches: Although tanabata patterns don’t overlap with each other, in general KMP, j = failure[j-1] correctly counts overlapping matches (e.g., searching for pattern aa in text aaa yields 2 matches)

   Source Code

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()

---

This editorial was generated by claude4.5opus.