请在UVA/SPOJ/atcoder/codeforces题库中查找原题，并给出c++代码以及思路：非混淆对话的兴奋水平是奶牛双重发送的次数，即S中子串BB或EE出现的次数。您想找到原始消息的兴奋水平，但您不知道哪些是Bessie / Elsie发送的Farmer John的消息。在所有可能性上，输出S的所有可能兴奋水平。

题目链接：

UVA 12404 Excitement Levels

SPOJ EXCITE - Excitement Levels

Codeforces 583E - Watching Fireworks is Fun

题意概述：

有两只奶牛Bessie和Elsie通过一个电话线交换消息，每条消息可能是Bessie发出的、Elsie发出的，或两只奶牛都发出的。我们将Bessie和Elsie发出的消息的序列表示为两个字符串$B$和$E$，其中$B$表示Bessie发送的消息，$E$表示Elsie发送的消息。例如：当$B = \texttt{AEABBABA}$且$E = \texttt{BEABEAE}$时，下表描述了这两只奶牛之间的一些有可能的信息交换：

$$
\begin{array}{|c|c|c|}
\hline \textbf{位置} & \textbf{消息} & \textbf{发送方} \\
\hline 1 & A & B \\
\hline 2 & E & E \\
\hline 3 & A & E \\
\hline 4 & B & B \\
\hline 5 & A & E \\
\hline 6 & B & A \\
\hline 7 & A & B \\
\hline 8 & E & A \\
\hline 9 & - & - \\
\hline
\end{array}
$$

对于给定的字符串$B$和$E$，我们可以尝试恢复出她们发送的所有消息。让$S$表示任意一种可能的恢复方案中，两只奶牛发送的所有消息组成的序列。例如：上表中的恢复方案为$\texttt{AEABBAEAB}$，其中有两个BB子串和两个EE子串。我们将$S$中BB子串和EE子串的总数称为这个方案的兴奋水平。

现在，给定$B$和$E$，请你计算出所有可能的兴奋水平，并把它们按从小到大的顺序输出。

题解：

一些定义：

$B$的长度为$n$。

$E$的长度为$m$。

如果我们知道了一个恢复方案，那么我们可以在$O(n + m)$的时间内判断它的兴奋水平。具体来说，我们可以使用一个单调栈来计算所有在$S$中以BB或EE为结尾的子串的数量，其中栈中存储了在$S$中以B或E为结尾的子串的个数。

根据上面的定义，我们可以发现给定任意一个$S$，我们可以用单调栈在$O(n + m)$的时间内计算出$S$的兴奋水平，但是一个字符串有$n + m - 1$个位置，因此存在$(n + m - 1)!$多种可能的$S$。我们显然不能枚举所有的$S$。

解决方案：

我们可以直接计算出所有满足条件的$S$。具体来说，我们可以在一个递归的函数中，构建一个字符数组$S$，表示目前为止我们已经选择了哪些字符。在每个递归调用中，我们都会向$S$中添加一个字符——当前字符序列中次数较少的一个字符。如果$S$已经被填满，那么我们就可以在$O(n + m)$的时间内计算出当前方案的兴奋水平，并将其添加到答案数组中。这个递归函数的时间复杂度为$O((n + m)! (n + m))$，空间复杂度也为$O((n + m)!)$。在本题的数据范围内，这个算法可以通过本题。

代码：