一个最朴素的方法:枚举每个区间(C(n,2)个 ),计算区间中极长段的个数。 时间复杂度O(n2) , n=1e5,n2=1e10>1e8 , 超时。
考虑原串其中的某一个极长段对总体答案的贡献:
小红最近迷上了字符串,并且认为一个字符串的美好值为字符串内,连续相同子串的数量。例如“aabbccddef”的美好值为6。
小红的朋友给了他一个01串,已经迷恋上字符串的小红想知道,这个01串所有子串的美好值之和是多少?
注:一共有Cn+12个子串
第一行输入一个正整数n,代表字符串的长度。
第二行为n长的01串。
1≤n≤2∗105
一个整数
输入
4
0011
输出
14
说明
子串分别为:0,0,1,1,00,01,11,001,011,0011
美好值分别为:1,1,1,1,1,2,1,2,2,2
总美好值为:14