题目链接
题意
- 如果字符串y在字符串x中出现n次,那么F(x,y)=n*(n+1)/2 (可以看做是一个长为n的区间,求滑动区块的总个数)
- 现在给一个字符串,求所有的F(s,x)的和,x为字符串的所有不相同的子串.
思路
- 直接SAM
- right[v]就是SAM上状态表示的所有字符串出现的次数
- 那么每个状态的答案就是right[v](right[v]+1)/2*(st[v].len-st[st[v].link].len)
- 前面right[v](right[v]+1)/2是串的组合
- 后面是 st[v].len - st[st[v].link].len是后缀的前缀长度,是本质不同的串的贡献
- 也即后缀的前缀每个字母的贡献—->就是 每个后缀节点t跳父亲节点fa跳掉的那部分t的前缀 中的 以每一个字母开头的串t的后缀 都是和串t所在状态节点出现次数(前面的串的组合数)相同的!
- 累加答案完成计算
AC代码
1 |
|
参考
每天一句叨叨
路还长,别太狂,以后指不定谁辉煌