P2743 [USACO5.1] Musical Themes

We represent a piece of music by a sequence of $N$ ($1 \le N \le 5000$) notes, each an integer in the range $1 \sim 88$, where each number denotes a key on the piano. Unfortunately, this way of encoding a melody ignores note durations, but this programming task concerns pitch only and is independent of duration. Many composers build a piece around a recurring "theme". In our representation, a "theme" is a substring of the entire note sequence that satisfies the following conditions: 1. Its length is at least $5$ notes. 2. It appears repeatedly in the piece (possibly after transposition, see below). 3. The repeated occurrences of the same theme must be non-overlapping. "Transposition" means that each note in the theme sequence is increased or decreased by the same integer. Given a piece, compute the length (number of notes) of the longest theme. The time limit for this problem is $1$ second.

The first line of input contains the integer $N$. Each of the following lines (except possibly the last) contains $20$ integers representing the note sequence. The last line may contain fewer than $20$ notes.

Output a single integer, the length of the longest theme. If there is no theme, output `0`.

The statement is translated from NOCOW. USACO Training Section 5.1. Translated by ChatGPT 5