题面
考虑字符串 s 仅由小写字母组成，例如 "abba"。定义 W(s) 为 s 所有本质不同的连续子串的集合，例如 W("abba") = { "a","b","ab","ba","bb","abb","bba","abba" }。
定义 Y(s) 为 s 所有本质不同的非连续子串的集合，例如 Y("abba") = W("abba") ∪ { "aa","aba" }，显然 W(s)是 Y(s) 的子集。
对于一些奇怪的字符串 s 满足 W(s) = Y(s)，例如 "abba" 就不是奇怪的，但 "abb" 是奇怪的。因为 W(s) = Y(s) = { "a","b","ab","bb","abb" }。现在小明有一个字符串 s，请你求出 W(s)中有多少个字符串是奇怪的？
注意：集合中的所有元素互不相同
分析
显然奇怪的只有两种，要么是aabb型要么是aaaa型，即不能由超过三部分组成。
对于aaaa型很简单，只需要统计连续的相同字母的数量的最长是多少。
对于aabb型，会有很多重复的情况，怎么计算呢？
考虑这两个 aaabb和aabbb，如果按2*3和3*2分别算，显然中间有重复计算，算了aaabb的2*3后，第二个具有的贡献仅有abbb和aabbb，即（3-2）*2
这是不是很像一个区间覆盖问题？我们把一个aabb型的写成（l,r）的点对形式，上面这两个分别是（3,2）和（2,3）
我们对于相同的两个字母（上面是a,b），把他们按l从小到大排序，如果r超过了之前最大的r，则会产生l*(r-maxr ) 的贡献，就像上面的2*（3-2）一样
对于aab这种，显然已经被完全覆盖了，又因为它的r并没有超过maxr，所以它也自然不会被计算。
代码
#include<bits/stdc++.h> using namespace std; #define N 200020 int n,ans; int len[30]; char s[N]; struct email{int l,r;}; vector<email>v[30][30]; bool cmp(email a,email b){return a.l>b.l;} void pre() { int i=1,j,l=1,r;char ml=s[1],mr; while(s[i]==s[i+1])i++,l++; while(i<n) { j=i+1;mr=s[j];r=1; while(j<n&&s[j]==s[j+1])j++,r++; v[ml-'a'][mr-'a'].push_back((email){l,r}); i=j,l=r,ml=mr; } } inline void cal(int x,int y) { sort(v[x][y].begin(),v[x][y].end(),cmp); int i=0;email p=v[x][y][i]; int ml=p.l,mr=p.r;ans+=ml*mr;i++; for(;i<v[x][y].size();i++) { email p=v[x][y][i]; if(mr<p.r)ans+=p.l*(p.r-mr),mr=p.r; } } int main() { scanf("%s",s+1);n=strlen(s+1); for(int i=1;i<=n;) { int j=i; while(j<n&&s[j]==s[j+1])j++; len[s[i]-'a']=max(len[s[i]-'a'],j-i+1); i=j+1; } for(int i=0;i<26;i++)ans+=len[i]; pre(); for(int i=0;i<26;i++) for(int j=0;j<26;j++) if(v[i][j].size()) cal(i,j); printf("%d ",ans); return 0; }