首先,我们可以考虑枚举每个子串,然后计算出每个子串出现的次数,最后将所有子串出现次数相加即可得到文章的复杂度。但是,这样的时间复杂度是 O(n^3),无法通过本题。
接下来,我们考虑优化计算每个子串出现次数的过程。对于一个子串 s,我们可以考虑它的出现次数与它的前缀和后缀有关。具体来说,设 f(i) 表示以第 i 个字符结尾的子串中,有多少个子串与 s 相同的前缀。那么,s 在文章中出现的次数就是 \sum_{i=1}^n f(i)
接下来,我们考虑如何计算 f(i)。对于 f(i),我们可以枚举 s 的每个前缀 t,然后判断 t 是否是以第 i 个字符结尾的子串的前缀。如果是,那么 f(i) 就需要加上 t 的长度。具体来说,设 g(i,j) 表示以第 i 个字符结尾的子串中,有多少个子串与 s 的前 j 个字符相同。那么,f(i) 就可以表示为:
f(i) = \sum_{j=1}^{|s|} g(i,j) \times (|s|-j+1)
接下来,我们考虑如何计算 g(i,j)。对于 g(i,j),我们可以考虑使用哈希来判断两个字符串是否相同。具体来说,我们可以预处理出 s 的所有前缀的哈希值,然后对于以第 i 个字符结尾的子串,我们可以计算出它的哈希值,然后与 s 的前 j 个字符的哈希值进行比较。如果相同,那么 g(i,j) 就需要加上 1。