Submission #1799538

---

Source Code Expand

from collections import deque
base = ord('a')
root = [None]*30
root[-2] = 0; root[-3] = 0
def add(s):
    node = root
    for c in s:
        code = ord(c) - base
        child = node[code]
        if not child:
            node[code] = child = [None]*30
            child[-2] = node[-2] + 1
            child[-3] = 0
        node = child
    node[-3] = 1
def suffix():
    que = deque([root])
    while que:
        v = que.popleft()
        for i in range(26):
            if not v[i]:
                if v[-1]:
                    v[i] = v[-1][i]
                else:
                    v[i] = root[i] or root
                continue
            if v[-1]:
                v[i][-1] = v[-1][i]
            else:
                v[i][-1] = root
            que.append(v[i])
    root[-1] = root
ls = set()
vs = []

N = int(input())
for i in range(N):
    s = input()
    add(s)
    ls.add(len(s))
suffix()

t = input()
tl = len(t)

MOD = 10**9 + 7

dp = [0]*(tl + 1)
dp[0] = 1
for l in ls:
    vs.append(l)
*rng, = range(len(vs))
srcs = [root] * len(ls)
for i in range(tl):
    code = ord(t[i]) - base
    for j in rng:
        l = vs[j]
        current = srcs[j] = srcs[j][code]
        if current[-2] == l:
            if current[-3]:
                dp[i+1] += dp[i-l+1]
                dp[i+1] %= MOD
            srcs[j] = current[-1]
print(dp[tl])

Submission Info

Judge Result