Morse Code
Contest: Codeforces Round 542 [Alex Lopashev Thanks-Round] (Div. 1)
Difficulty rating: 2400
Tags: binary search, data structures, dp, hashing, sortings, string suffix structures, strings

In Morse code, an letter of English alphabet is represented as a string of some length from $$$1$$$ to $$$4$$$. Moreover, each Morse code representation of an English letter contains only dots and dashes. In this task, we will represent a dot with a "0" and a dash with a "1".

Because there are $$$2^1+2^2+2^3+2^4 = 30$$$ strings with length $$$1$$$ to $$$4$$$ containing only "0" and/or "1", not all of them correspond to one of the $$$26$$$ English letters. In particular, each string of "0" and/or "1" of length at most $$$4$$$ translates into a distinct English letter, except the following four strings that do not correspond to any English alphabet: "0011", "0101", "1110", and "1111".

You will work with a string $$$S$$$, which is initially empty. For $$$m$$$ times, either a dot or a dash will be appended to $$$S$$$, one at a time. Your task is to find and report, after each of these modifications to string $$$S$$$, the number of non-empty sequences of English letters that are represented with some substring of $$$S$$$ in Morse code.

Since the answers can be incredibly tremendous, print them modulo $$$10^9 + 7$$$.

Input format:
The first line contains an integer $$$m$$$ ($$$1 \leq m \leq 3\,000$$$) — the number of modifications to $$$S$$$.

Each of the next $$$m$$$ lines contains either a "0" (representing a dot) or a "1" (representing a dash), specifying which character should be appended to $$$S$$$.

Output format:
Print $$$m$$$ lines, the $$$i$$$-th of which being the answer after the $$$i$$$-th modification to $$$S$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Let us consider the first sample after all characters have been appended to $$$S$$$, so S is "111".

As you can see, "1", "11", and "111" all correspond to some distinct English letter. In fact, they are translated into a 'T', an 'M', and an 'O', respectively. All non-empty sequences of English letters that are represented with some substring of $$$S$$$ in Morse code, therefore, are as follows.

1. "T" (translates into "1")
2. "M" (translates into "11")
3. "O" (translates into "111")
4. "TT" (translates into "11")
5. "TM" (translates into "111")
6. "MT" (translates into "111")
7. "TTT" (translates into "111")

Although unnecessary for this task, a conversion table from English alphabets into Morse code can be found here.

Example input:
3
1
1
1

Example output:
1
3
7

Example input:
5
1
0
1
0
1

Example output:
1
4
10
22
43

Editorial:
We will be computing the answers offline instead of doing so immediately after each modification.
Let $$$T = S_{reversed}$$$. Now, we need to find the number of English sequences that, if considered backward, would translate into some substring of each suffix of T.
Let $$$f(l, r)$$$ be the number of English sequences that translate to exactly $$$T[l..r]$$$.
Let $$$g(l, r)$$$ be sum of $$$f(l, x)$$$ over all $$$l \leq x \leq r$$$.
Note that $$$f(l, r)$$$ can be calculated with dynamic programming for all $$$1 \leq l \leq r \leq m$$$ in $$$\mathcal{O}(km^2)$$$ where $$$k$$$ denotes the longest length of an English alphabet in Morse code (which is $$$4$$$). Following that, we can calculate $$$g(l, r)$$$ for all $$$1 \leq l \leq r \leq m$$$ in $$$\mathcal{O}(m^2)$$$.
The answer for the suffix $$$T[x..m]$$$ is simply the sum of $$$g(i, m)$$$ over all $$$x \leq i \leq m$$$ subtracted by the number of over-counted English sequences. The number of over-counted sequences can be calculated by considering the suffix array of $$$T$$$. Namely, for each two adjacent suffixes in the list, we over-counted them by $$$g(l, r)$$$ with $$$l$$$ and $$$r$$$ denoting the corresponding indices of their longest common prefix (LCP).
Therefore, the answer for $$$T[1..m]$$$ is $$$\sum\limits_{1 \leq i \leq m} g(i, m)$$$ subtracted by the sum of $$$g(l, r)$$$ of the LCP between each pair of adjacent suffixes.
Transitioning to solve the problem for $$$T[x'..m]$$$ where $$$x' = x+1$$$ can be done efficiently, since the removal character of the string affects only one entry in the suffix list.
To sum up, we find $$$g(l, r)$$$ for all valid $$$l$$$ and $$$r$$$ in $$$\mathcal{O}(km^2)$$$. Then, we sort the suffixes naively in $$$O(m^2 \log m)$$$, before computing the answer in the final step in $$$\mathcal{O}(m^2)$$$.
The time complexity is $$$\mathcal{O}(km^2 + m^2 \log m)$$$.