Open forever97 opened 4 years ago
https://forever97.github.io/2019/09/11/HACKERRANKhowmanysubstrings/
Problem给定长度为$n(n \le 10^5)$的字符串求区间本质不同的子串数量 Solution我们用线段树维护每个节点为左端点的，到r为右端点为止的本质不同子串数量 每个相同的子串只将值保留在最后一次出现的左端点 当一个字符被新增到原串的末尾时，会在某些左端点增加新的本质不同的串 同时部分子串最后一次出现的左端点将移动到串尾 我们对$[1,pos]$前缀的所有左端点答案$+1$，考虑减去
https://forever97.github.io/2019/09/11/HACKERRANKhowmanysubstrings/
Problem给定长度为$n(n \le 10^5)$的字符串求区间本质不同的子串数量 Solution我们用线段树维护每个节点为左端点的，到r为右端点为止的本质不同子串数量 每个相同的子串只将值保留在最后一次出现的左端点 当一个字符被新增到原串的末尾时，会在某些左端点增加新的本质不同的串 同时部分子串最后一次出现的左端点将移动到串尾 我们对$[1,pos]$前缀的所有左端点答案$+1$，考虑减去