A6047. 「2017 山东一轮集训 Day5」字符串
编程题
提高+/省选-
知识点
题目描述
给定 $ n $ 个字符集为小写字母的字符串 $ s_i $，一个串 $ t $ 是可接受的，当且仅当 $ t $ 可以表示成 $ p_1 + p_2 + \cdots + p_n $，其中 $ p_i $ 为 $ s_i $ 的一个子串（可以为空），$ + $ 表示字符串的拼接。问有多少种本质不同的字符串 $ t $ 是可接受的。答案对 $ 10 ^ 9 + 7 $ 取模。
输入格式
第一行一个整数 $ n $。
接下来 $ n $ 行，每行一个字符串 $ s_i $。
接下来 $ n $ 行，每行一个字符串 $ s_i $。
输出格式
输出一行一个整数，表示可接受的字符串的数目对 $ 10 ^ 9 + 7 $ 取模后的结果。
输入输出样例
输入 #1
2 bbbaa bb
输出 #1
30
说明/提示
第 1、2 个测试点，满足 $ n \leq 5, |s_i| \leq 7 $；
第 3 个测试点，满足 $ n = 1 $；
第 4 个测试点，满足 $ n = 2 $；
第 5、6 个测试点，满足 $ \sum\limits_{i = 1} ^ n |s_i| \leq 1000 $；
第 7、8、9、10 个测试点，满足 $ n \leq 10 ^ 6; \sum\limits_{i = 1} ^ n |s_i| \leq 10 ^ 6 $。
第 3 个测试点，满足 $ n = 1 $；
第 4 个测试点，满足 $ n = 2 $；
第 5、6 个测试点，满足 $ \sum\limits_{i = 1} ^ n |s_i| \leq 1000 $；
第 7、8、9、10 个测试点，满足 $ n \leq 10 ^ 6; \sum\limits_{i = 1} ^ n |s_i| \leq 10 ^ 6 $。