I. Fake News (hard)

Codeforces

IDCF802I

Time5000ms

Memory256MB

Difficulty—

string suffix structures

English · Original

Chinese · Translation

Formal · Original

Now that you have proposed a fake post for the HC2 Facebook page, Heidi wants to measure the quality of the post before actually posting it. She recently came across a (possibly fake) article about the impact of fractal structure on multimedia messages and she is now trying to measure the self-similarity of the message, which is defined as where the sum is over all nonempty strings _p_ and is the number of occurences of _p_ in _s_ as a **substring**. (Note that the sum is infinite, but it only has a finite number of nonzero summands.) Heidi refuses to do anything else until she knows how to calculate this self-similarity. Could you please help her? (If you would like to instead convince Heidi that a finite string cannot be a fractal anyway – do not bother, we have already tried.) ## Input The input starts with a line indicating the number of test cases _T_ (1 ≤ _T_ ≤ 10). After that, _T_ test cases follow, each of which consists of one line containing a string _s_ (1 ≤ |_s_| ≤ 100 000) composed of lowercase letters (_a_\-_z_). ## Output Output _T_ lines, every line containing one number – the answer to the corresponding test case. [samples] ## Note A string _s_ contains another string _p_ as a substring if _p_ is a contiguous subsequence of _s_. For example, _ab_ is a substring of _cab_ but not of _acb_.

既然你已经为 HC#cf_span[2] Facebook 页面提出了一条虚假帖子，Heidi 希望在实际发布之前评估该帖子的质量。她最近读到一篇（可能是虚假的）文章，讨论了分形结构对多媒体信息的影响，现在她试图测量该信息的自相似性，其定义为其中求和遍历所有非空字符串 #cf_span[p]，而是 #cf_span[p] 在 #cf_span[s] 中作为 *子串* 出现的次数。（注意，该求和是无限的，但仅有有限个非零项。） Heidi 在弄清楚如何计算这个自相似性之前，拒绝做任何其他事情。你能帮帮她吗？（如果你想要说服 Heidi 无论如何有限字符串都不可能是分形——别费劲了，我们已经试过了。）输入的第一行包含测试用例的数量 #cf_span[T]（#cf_span[1 ≤ T ≤ 10]）。接下来是 #cf_span[T] 个测试用例，每个测试用例包含一行，由小写字母（_a_-_z_）组成的字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 100 000]）。请输出 #cf_span[T] 行，每行包含一个数字——对应测试用例的答案。字符串 #cf_span[s] 包含另一个字符串 #cf_span[p] 作为子串，当且仅当 #cf_span[p] 是 #cf_span[s] 的一个连续子序列。例如，_ab_ 是 _cab_ 的子串，但不是 _acb_ 的子串。 ## Input 输入的第一行包含测试用例的数量 #cf_span[T]（#cf_span[1 ≤ T ≤ 10]）。接下来是 #cf_span[T] 个测试用例，每个测试用例包含一行，由小写字母（_a_-_z_）组成的字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 100 000]）。 ## Output 请输出 #cf_span[T] 行，每行包含一个数字——对应测试用例的答案。 [samples] ## Note 字符串 #cf_span[s] 包含另一个字符串 #cf_span[p] 作为子串，当且仅当 #cf_span[p] 是 #cf_span[s] 的一个连续子序列。例如，_ab_ 是 _cab_ 的子串，但不是 _acb_ 的子串。

Let $ s $ be a string of length $ n $. The self-similarity of $ s $ is defined as: $$ \sum_{\substack{p \in \Sigma^+ \\ p \text{ is a substring of } s}} (\text{occ}(p, s))^2 $$ where: - $ \Sigma^+ $ denotes the set of all nonempty strings over the alphabet $ \{a, b, \dots, z\} $, - $ \text{occ}(p, s) $ is the number of occurrences of substring $ p $ in $ s $ (counting overlapping occurrences). Equivalently, since only substrings of $ s $ contribute nonzero terms, we may write: $$ \sum_{\substack{p \subseteq s \\ |p| \geq 1}} (\text{occ}(p, s))^2 $$ where the sum is over all nonempty contiguous substrings $ p $ of $ s $, and $ \text{occ}(p, s) $ counts how many times $ p $ appears as a contiguous substring in $ s $. **Input:** - $ T $ test cases. - For each test case, a string $ s $ of length $ 1 \leq |s| \leq 100{,}000 $, consisting of lowercase English letters. **Output:** - For each test case, output the value of the above sum.

Samples

Input #1

4
aa
abcd
ccc
abcc

Output #1

API Response (JSON)

{
  "problem": {
    "name": "I. Fake News (hard)",
    "description": {
      "content": "Now that you have proposed a fake post for the HC2 Facebook page, Heidi wants to measure the quality of the post before actually posting it. She recently came across a (possibly fake) article about th",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF802I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Now that you have proposed a fake post for the HC2 Facebook page, Heidi wants to measure the quality of the post before actually posting it. She recently came across a (possibly fake) article about th...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "既然你已经为 HC#cf_span[2] Facebook 页面提出了一条虚假帖子，Heidi 希望在实际发布之前评估该帖子的质量。她最近读到一篇（可能是虚假的）文章，讨论了分形结构对多媒体信息的影响，现在她试图测量该信息的自相似性，其定义为\n\n其中求和遍历所有非空字符串 #cf_span[p]，而  是 #cf_span[p] 在 #cf_span[s] 中作为 *子串* 出现的次数。（注意，该...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ s $ be a string of length $ n $. The self-similarity of $ s $ is defined as:\n\n$$\n\\sum_{\\substack{p \\in \\Sigma^+ \\\\ p \\text{ is a substring of } s}} (\\text{occ}(p, s))^2\n$$\n\nwhere:\n- $ \\Sigma^+ $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments