天下一コン2014 予選B B - エターナルスタティックファイナル

問題原文

解法

dp。

$dp[i\rbrack := S[0: i\rbrack$ を構築する通り数

としてdpテーブルを順に埋めていく。

実装

なんだろう、拾う方が気持ちイメージが楽な気がします。
今 $i$ までを見ていて、最後に $t$ を使ってできるかな〜？というきもち

N = int(input())
S = input()
lenS = len(S)
T = [input() for _ in range(N)]
MOD = 10 ** 9 + 7

dp = [0] * (lenS + 1)
dp[0] = 1

for i in range(lenS + 1):
    for t in T:
        if i - len(t) < 0:
            continue
        if S[i - len(t):i] == t:
            dp[i] += dp[i - len(t)]
            dp[i] %= MOD

print(dp[-1] % MOD)

感想

いつものノリで「 $i$ 番目までみたときに〜」でなんとなく書いたら、 $S =$ aaaa で a と aa がある時に、 aa a を取れなくて悲しくなった。
$S[0: i\rbrack$ を見る時に、全ての $t$ について $S[0: i - 1\rbrack$ までの計算を終わらせておく必要がありそう。