(Analysis by Danny Mittal, Benjamin Qi)

Let's first consider the easier problem of computing $B(s)$ for a single string $s$. We can employ a greedy strategy:

Find the first occurrence of 'b' in $s$, then find the first occurrence of 'e' after the 'b', then find the first occurrence of 's' after that, find the first occurrence of 's' after that 's', find the first occurrence of 'i' after that, and then find the first occurrence of 'e' after that. Now we have all the letters in "bessie", and we can delete the letters in between them to get an occurrence of "bessie" in $s$. Then, we continue the greedy algorithm on the part of $s$ after that "bessie", until we reach the end of $s$. Since we just go through $s$ once, this is linear time.

The string has length at most $5000$

The problem is equivalent to finding the sum of $B(s)$ over all prefixes $s$ of $u$, doing so for all suffixes $u$ of $t$ and summing the results. We will therefore solve that problem for a given $u$ in $\mathcal O(|u|)$, then apply it to all suffixes of $t$, yielding an $\mathcal O(|t|^2)$ solution overall.

Consider applying the greedy algorithm we used for a single $s$ to all prefixes $s$ of $u$. Because the greedy algorithm just repeatedly finds the earliest occurrence of the characters in "bessie", the instances it finds will be the same for all prefixes of $u$; at least, it will be the same for those prefixes $s$ which are long enough to contain that instance.

This means that we can apply the greedy strategy on just $u$ itself, and whenever we find a complete "bessie", we count it for all prefixes which are long enough to contain it. Formally, if there are $k$ characters after an instance of "bessie" that we find, then we add $k + 1$ to the answer.

This takes time linear in the length of $u$ as desired.

We want to optimize the $O(|u|^2)$ solution by simulating all of the greedy algorithms at once. We can do this by noticing that each greedy algorithm can be viewed as a single "token" that's located at some position in the string "bessie". Whenever we encounter the corresponding character of "bessie" in $u$, we move to the next position, and whenever we move past the last character we add $k + 1$ to the answer and move back to the first position in "bessie".

It therefore suffices to go through $t$ itself, and maintain the number of tokens at each position of "bessie". Whenever we look at a character $c$ in $t$, we first add a new token at the first position of "bessie", then move all tokens at a position with character $c$ one step to the right. Whenever we see an "e", if there are $k$ characters remaining in $t$, we add $k + 1$ multiplied by the number of tokens at the end of "bessie" to our answer and move that amount of tokens back to the beginning of "bessie".

This takes time linear in the length of $t$ which is fast enough.

Danny's code:

import java.io.BufferedReader;
import java.io.IOException;

public class Pareidolia {

public static void main(String[] args) throws IOException {
long[] waiting = new long;
long rem = string.length();
for (char letter : string.toCharArray()) {
waiting++;
for (int d = 5; d >= 0; d--) {
if (letter == "bessie".charAt(d)) {
waiting[d + 1] += waiting[d];
waiting[d] = 0;
}
}
waiting += waiting;
waiting = 0;
rem--;
}
}
}


For each $i$ from $|t|$ down to $0$, let's compute $total[i]$, the sum of $B(u)$ for all prefixes $u$ of $t[i\dots |t|-1]$ The answer equals the sum of $total[i]$ for all $i$. Define $lst[i]$ to be the minimum index such that $t[i\dots lst[i]-1]$ contains an occurrence of "bessie", or $|t|+1$ if no such index exists. Then if we run the greedy algorithm on $t[i\dots j-1]$:

• If $j<lst[i]$, then the greedy algorithm does not find any "bessie"s.
• Otherwise, if $lst[i]\le j\le |t|$, then the greedy algorithm finds a "bessie" and restarts at $lst[i]$.

It follows that $total[i] = |t|+1-lst[i]+total[lst[i]]$. We can compute $lst$ from left to right by maintaining monotonic pointers $idx, \dots, idx$, one for each character of "bessie". To compute $lst[i]$, while there exists some $j$ such that $\texttt{"bessie"}[j] \neq idx[j]$ or $idx[j]< \begin{cases} idx[j-1]+1 & j > 0 \\ i & j = 0 \end{cases}$, increase $idx[j]$. Once we have finished processing all increases, $t[idx], t[idx], \dots, t[idx]$ form the earliest occurrence of "bessie" in $t[i\dots |t|-1]$, so $lst[i]=idx+1$.

As each pointer moves at most $|t|$ times in total, we can compute all entries of $lst$ in $O(|t|)$ total time. After computing $lst$, we can finish by computing $total$ in $O(|t|)$ time.

Ben's code:

t = input()
target = "bessie"
idx =  * len(target)
ans = float("inf")
lst = [-1] * len(t)

for i in range(len(t)):
for j in range(len(target)):
idx[j] = max(idx[j], i if j == 0 else idx[j - 1] + 1)
while idx[j] < len(t) and t[idx[j]] != target[j]:
idx[j] += 1
lst[i] = min(idx[-1], len(t)) + 1

total =  * (len(t) + 1)  # total[i] = sum of answers for prefixes of t[i:]
for i in reversed(range(len(lst))):
total[i] = len(lst) + 1 - lst[i]
if total[i] > 0:
total[i] += total[lst[i]]

print(sum(total))