CF123D String

    • 19通过
    • 43提交
  • 题目来源 CodeForces 123D
  • 评测方式 RemoteJudge
  • 标签 后缀数组,SA 排序 线段树
  • 难度 NOI/NOI+/CTSC
  • 时空限制 2000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    给你一个字符串s。每一组数字l和r满足$1 <= l <= r <= |s|$,他们对应s的子字符串(从l至r并包括l,r)

    现定义以一个形如F(string x, string y)的字符串函数。我们将要找到一个列表,其中字符串x的子串等于字符串y。我们根据配对的第一个数字的增加来对这组配对进行排序。函数$f(x,y)$的值等于列表中非空连续序列的数目。 例如:f(babbabbababbab,babb) = 6

    • (1, 4)
    • (4, 7)
    • (9, 12) 它的连续序列为:
    • (1, 4)(4, 7)
    • (4, 7)(9, 12)
    • (1, 4)(4, 7)(9, 12)

    给定字符串s,求所有f(s, x)的和 (x为s的字串)

    输入样例1解释:

    • f(aaaa,a):

      (1),(2),(3),(4)

    (1)(2),(2)(3), (3)(4)

    (1)(2)(3), (2)(3)(4)

    (1)(2)(3)(4)

    $f(aaaa,a)= 10$

    以此类推, $f(aaaa,aa)=6$

    $f(aaaa, aaa) = 3$

    $f(aaaa, aaaa) = 1$

    所以结果为10+6+3+1=20

    题目描述

    You are given a string $ s $ . Each pair of numbers $ l $ and $ r $ that fulfill the condition $ 1<=l<=r<=|s| $ , correspond to a substring of the string $ s $ , starting in the position $ l $ and ending in the position $ r $ (inclusive).

    Let's define the function of two strings $ F(x,y) $ like this. We'll find a list of such pairs of numbers for which the corresponding substrings of string $ x $ are equal to string $ y $ . Let's sort this list of pairs according to the pair's first number's increasing. The value of function $ F(x,y) $ equals the number of non-empty continuous sequences in the list.

    For example: $ F(babbabbababbab,babb)=6 $ . The list of pairs is as follows:

    $ (1,4),(4,7),(9,12) $

    Its continuous sequences are:

    • $ (1,4) $
    • $ (4,7) $
    • $ (9,12) $
    • $ (1,4),(4,7) $
    • $ (4,7),(9,12) $
    • $ (1,4),(4,7),(9,12) $

    Your task is to calculate for the given string $ s $ the sum $ F(s,x) $ for all $ x $ , that $ x $ belongs to the set of all substrings of a string $ s $ .

    输入输出格式

    输入格式:

    The only line contains the given string $ s $ , consisting only of small Latin letters ( $ 1<=|s|<=10^{5} $ ).

    输出格式:

    Print the single number — the sought sum.

    Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specificator.

    输入输出样例

    输入样例#1: 复制
    aaaa
    
    输出样例#1: 复制
    20
    
    输入样例#2: 复制
    abcdef
    
    输出样例#2: 复制
    21
    
    输入样例#3: 复制
    abacabadabacaba
    
    输出样例#3: 复制
    188
    

    说明

    In the first sample the function values at $ x $ equal to "a", "aa", "aaa" and "aaaa" equal 10, 6, 3 and 1 correspondingly.

    In the second sample for any satisfying $ x $ the function value is 1.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。