校园网站建设服务广告网站

久违的字符串计数题。

显然只用考虑$[i:j]$这一段拼成的串。不难得出结论：设$nx{t}_i$表示$i$之后第一个本质不同的字符的位置，那么$nx{t}_i\le j$，并且$s_i?s_{nx{t}_i}$，或者$nx{t}_i>j$。

注意到限制对于左端点$l$是固定的。对于左端点，保留最紧的，也就是$r$最大的限制。这样设$f_{i,j}$表示前缀$i$，且$s_i$等于$j$的答案，发现贡献是一段区间，可以差分搞一下。可能稍微有一点麻烦。

注意不要算重。

复杂度$O(26n)$。