#PQJ2879x16201. QOJ 2879_16201

    ID: 2879 传统题 2000ms 2048MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SCOI 2024字符串后缀数组

QOJ 2879_16201

CCF NOI 2024 四川省代表队评测活动 第一试 字符串(string) 字符串(string) 【题目描述】 给定 𝑛 个 𝑠 串,𝑚 个 𝑡 串。𝑓(𝑖, 𝑗, 𝑘, 𝑙) 表示 𝑠𝑖+ 𝑡𝑗 作为 𝑠𝑘+ 𝑡𝑙 的子串出现的次数,字符 串 𝑎+ 𝑏 表示将 𝑏 直接拼接在 𝑎 后面,求 ∑ 𝑛 𝑖=1 ∑ 𝑚 𝑗=1 ∑ 𝑛 𝑘=1 ∑ 𝑚 𝑙=1 𝑓(𝑖, 𝑗, 𝑘, 𝑙) 的值。由于答案很大,请输出其对 109 + 7 取模后的值。 对于字符串 𝑎, 𝑏,字符串 𝑎+ 𝑏 表示将 𝑏 直接拼接在 𝑎 的后面。例如:若字符串 𝑎 为 abc,字符串 𝑏 为 ab,则字符串 𝑎+ 𝑏 为 abcab。 对于非空字符串 𝑎, 𝑏,如果将 𝑎 删去某个前缀和某个后缀(可以为空)后与 𝑏 相同,则称 𝑏 为 𝑎 的子串。例如:对于字符串 abcd,字符串 a,bcd,bc 均是这个字符串的子串,而字 符串 acd,bd 不是这个字符串的子串。 【输入格式】 从文件 string.in 中读入数据。 输入的第一行包含两个整数 𝑛 和 𝑚。 接下来 𝑛 行,每行包含一个只由小写英文字母组成的字符串 𝑠𝑖。 接下来 𝑚 行,每行包含一个只由小写英文字母组成的字符串 𝑡𝑗。 【输出格式】 输出到文件 string.out 中。 输出一行一个整数,表示答案对 109 + 7 取模后的值。 【样例1 输入】 1 2 3 2 a 3 ba 4 b 5 bb 6 ab 【样例1 输出】 第2 页 共9 页

CCF NOI 2024 四川省代表队评测活动 第一试 字符串(string) 1 14 【样例2】 见选手目录下的 string/string2.in 与 string/string2.ans。 这个样例满足测试点 3 ∼6 的条件限制。 【样例3】 见选手目录下的 string/string3.in 与 string/string3.ans。 这个样例满足测试点 9 ∼12 的条件限制。 【样例4】 见选手目录下的 string/string4.in 与 string/string4.ans。 这个样例满足测试点 13 ∼20 的条件限制。 【数据范围】 对于所有测试数据保证:1 ≤𝑛, 𝑚≤105,1 ≤|𝑠𝑖|, |𝑡𝑗| ≤106,∑|𝑠𝑖|, ∑|𝑡𝑗| ≤106。 测试点编号 𝑛 𝑚 |𝑠𝑖|, |𝑡𝑖|, ∑|𝑠𝑖|, ∑|𝑡𝑗| 特殊性质 1 ∼2 ≤50 ≤50 ≤100 无 3 ∼6 ≤200 ≤200 ≤103 7 ∼8 ≤105 ≤105 ≤106 A 9 ∼12 = 1 无 13 ∼20 ≤105 特殊性质 A: 所有 𝑠 串只包含一种字母,所有 𝑡 串只包含与 𝑠 串不同的另一种字母。 第3 页 共9 页