#P9425. HDU 6761 Minimum Index

    ID: 5763 传统题 1000ms 256MiB 尝试: 3 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-Lyndon 分解Duval 算法线性 DP

HDU 6761 Minimum Index

题目描述

给定字符串 ss。对每个 1≤i≤∣s∣1\le i\le |s|,在前缀 s1s2⋯sis_1s_2\cdots s_i 的所有非空后缀中,找到字典序最小的一个。若较短的字符串是较长字符串的前缀,较短者字典序更小。

设该后缀在原字符串中的起始位置为 kik_i(下标从 11 开始)。求

$$\left(\sum_{i=1}^{|s|} k_i\cdot1112^{i-1}\right)\bmod (10^9+7).$$

输入格式

第一行一个整数 TT,表示测试组数。接下来 TT 行,每行一个非空字符串 ss,仅由小写英文字母组成。

输出格式

对每组数据输出一行一个整数,即上述和式取模后的结果。

1
aab
1238769

样例的三个前缀 a、aa、aab 对应的最小后缀依次为 a、a、aab,起始位置为 1,2,11,2,1,所以答案为 1+2⋅1112+111221+2\cdot1112+1112^2。

数据范围

1≤T≤1041\le T\le10^4,1≤∣s∣≤1061\le |s|\le10^6,所有字符串长度之和不超过 2×1072\times10^7。

HDU 6761 原题截图