← 返回题目列表

AtCoder · jag2017autumn_h

H. 单独的字符串

中文机器翻译题面 查看原题

问题陈述

给你一个字符串 $t$ 和一组 $S$ 的 $N$ 不同字符串。您需要分隔 $t$,以便每个部分都包含在 $S$ 中。

例如,以下4种分离方法满足$t = abab$且$S = \{a, ab, b\}$时的条件。

  • $a、b、a、b$
  • $a、b、ab$
  • $ab、a、b$
  • $ab, ab$

你的任务是计算分隔 $t$ 的方法的数量。由于结果可能很大,因此您应该输出除以 $1{,}000{,}000{,}007$ 的余数。


输入

输入由单个测试用例组成,格式如下。

$N$ $s_1$ $\vdots$ $s_N$ $t$

第一行由一个整数 $N \ (1 \le N \le 100{,}000)$ 组成,它是 $S$ 的元素数量。 以下 $N$ 行由 $N$ 个由换行符分隔的不同字符串组成。第 $i$ 个字符串 $s_i$ 表示 $S$ 的第 $i$ 个元素。 $s_i$ 由小写字母组成,长度在 $1$ 到 $100{,}000$(含)之间。 $s_{i} \ (1 \le i \le N)$ 的长度总和最多为 $200{,}000$。 下一行是字符串$t$,由小写字母组成,表示要分隔的字符串,长度在$1$到$100{,}000$(含)之间。

输出

计算分隔 $t$ 的方法数,并打印除以 $1{,}000{,}000{,}007$ 所得的余数。


样本输入 1

3
a
b
ab
abab

样本输入 1 的输出

4

示例输入 2

3
a
b
c
xyz

样本输入 2 的输出

0

示例输入 3

7
abc
ab
bc
a
b
c
aa
aaabcbccababbc

样本输入 3 的输出

160

示例输入 4

10
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa
aaaaaaaaa
aaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

样本输入 4 的输出

461695029