[Acwing | 蓝桥 ] 2868. 子串分值 贡献思想

前言

传送门 :

思路

结论 : 当前 字符 在该子串中的贡献为 ( i − p r e [ i ] ) ∗ ( n x t [ i ] − i ) (i-pre[i])*(nxt[i]-i) (i−pre[i])∗(nxt[i]−i)

解释 :

对于当前 以 i i i开头的子串,最多可以构造出 ( n x t [ i ] − i ) (nxt[i] - i) (nxt[i]−i)的串

例如 : 2 , 3 , 4 , 5 2,3,4,5 2,3,4,5

当前 i = 2 , n x t [ i ] = 5 i=2,nxt[i]=5 i=2,nxt[i]=5则可以构造出 5 − 2 = 3 5-2=3 5−2=3个子串 2 2 2 2 , 3 2,3 2,3 2 , 3 , 4 2,3,4 2,3,4

因此在于前面的数 根据乘法原理即可得上面的表达式

因此问题转换为 **求 n x t [ i ] nxt[i] nxt[i]和 p r e [ i ] pre[i] pre[i]**即可

我们只需要 O n On On的遍历即可

Mycode

const int N =  1e5+10;
int pre[N];
int nxt[N];
int last[N];

void solve(){
	string s;cin>>s;
	
	memset(last,-1,sizeof last);
	for(int i = 0;i