/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 266 点
問題文
高橋君は音楽が大好きで、お気に入りの曲の歌詞を集めたデータベースを作成しています。
高橋君は N 曲分の歌詞データを持っています。各曲には 1 から N までの番号が付けられており、i 番目の曲の歌詞は英小文字からなる文字列 S_i で表されています。
高橋君は、各曲の「夏らしさスコア」を計算することにしました。曲 i の夏らしさスコアは、文字列 S_i の中に連続する部分文字列（substring）として tanabata が出現する回数として定義されます。
より正確には、S_i の j 文字目を S_i[j]（1-indexed）と表すとき、S_i[j]S_i[j+1] \cdots S_i[j+7] が tanabata と一致するような整数 j（1 \leq j \leq |S_i| - 7）の個数です。ここで |S_i| は文字列 S_i の長さを表します。|S_i| \leq 7 の場合は該当する j が存在しないため、夏らしさスコアは 0 です。
N 曲の中で、夏らしさスコアが最大の曲の番号を求めてください。夏らしさスコアが最大の曲が複数ある場合は、そのうち番号が最も小さいものを出力してください。なお、すべての曲の夏らしさスコアが 0 である場合も同様に、番号が最も小さい曲（すなわち曲 1）を出力してください。
制約
- 1 \leq N \leq 10^5
- 1 \leq |S_i| \leq 10^5
- \sum_{i=1}^{N} |S_i| \leq 10^6
- S_i は英小文字からなる文字列
入力
N S_1 S_2 \vdots S_N
- 1 行目には、曲の数を表す整数 N が与えられる。
- 続く N 行のうち i 行目（1 \leq i \leq N）には、i 番目の曲の歌詞を表す文字列 S_i が与えられる。
出力
夏らしさスコアが最大の曲の番号を 1 行で出力してください。該当する曲が複数ある場合は、番号が最も小さいものを出力してください。
入力例 1
3 tanabata summer tanabatatanabata
出力例 1
3
入力例 2
5 abctanabatadef tanabata xxxxxxxxxx tanabatanabata holiday
出力例 2
4
入力例 3
10 thesummerstarfestivaltanabataisbeautiful tanabatatanabatatanabata abcdefghijklmnopqrstuvwxyz aaatanabatabbbtanabataccc summerbeachsernlight tanabatanabatanabatanabata zzzzzzzzzzzzzzzzzzzzz atanabatax tanabata mytanabatamemorytanabatadreamtanabatanight
出力例 3
6
Score : 266 pts
Problem Statement
Takahashi loves music and is building a database of lyrics from his favorite songs.
Takahashi has lyrics data for N songs. Each song is numbered from 1 to N, and the lyrics of the i-th song are represented by a string S_i consisting of lowercase English letters.
Takahashi decided to calculate a "summer score" for each song. The summer score of song i is defined as the number of times tanabata appears as a contiguous substring in the string S_i.
More precisely, letting S_i[j] denote the j-th character of S_i (1-indexed), the summer score is the number of integers j (1 \leq j \leq |S_i| - 7) such that S_i[j]S_i[j+1] \cdots S_i[j+7] matches tanabata. Here, |S_i| denotes the length of the string S_i. If |S_i| \leq 7, no such j exists, so the summer score is 0.
Among the N songs, find the number of the song with the maximum summer score. If there are multiple songs with the maximum summer score, output the one with the smallest number. Note that if all songs have a summer score of 0, likewise output the song with the smallest number (i.e., song 1).
Constraints
- 1 \leq N \leq 10^5
- 1 \leq |S_i| \leq 10^5
- \sum_{i=1}^{N} |S_i| \leq 10^6
- S_i is a string consisting of lowercase English letters
Input
N S_1 S_2 \vdots S_N
- The first line contains an integer N representing the number of songs.
- The i-th line (1 \leq i \leq N) of the following N lines contains the string S_i representing the lyrics of the i-th song.
Output
Output the number of the song with the maximum summer score on a single line. If there are multiple such songs, output the one with the smallest number.
Sample Input 1
3 tanabata summer tanabatatanabata
Sample Output 1
3
Sample Input 2
5 abctanabatadef tanabata xxxxxxxxxx tanabatanabata holiday
Sample Output 2
4
Sample Input 3
10 thesummerstarfestivaltanabataisbeautiful tanabatatanabatatanabata abcdefghijklmnopqrstuvwxyz aaatanabatabbbtanabataccc summerbeachsernlight tanabatanabatanabatanabata zzzzzzzzzzzzzzzzzzzzz atanabatax tanabata mytanabatamemorytanabatadreamtanabatanight
Sample Output 3
6