Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

繰り返す呪文

古代国家イワシロを発見し調査を進めた我々研究者は、ついにイワシロの中心部にある神殿を発見した。神殿にはイワシロの神にささげた石版が保管されていた。石版には、文章と呪文が一つずつ、２つの文字列が書かれていた。

イワシロでは呪文が文章の中に、何回現れるかが重要な意味を持つ。ただし、呪文に含まれるすべての文字が順番に、文章の中にとびとびで現れるものも１回現れていると考える。例えば、文章が"abab" で、呪文が "ab" であれば、連続でないものも含めて "ab" は "abab" の中に３回現われている（ abab, abab, abab の３通り）。

文章と呪文が与えられたとき、呪文が文章の中に何回現れるかを出力するプログラムを作成せよ。 

Input

入力は以下の形式で与えられる。 

t
b

１行目に、石版に書かれた文章を表す文字列tが与えられる。２行目に、石版に書かれた呪文を表す文字列bが与えられる。どちらの文字列も英小文字だけから成る、長さが1以上1000以下の文字列である。 

Output

呪文が文章の中に何回現れるかを１行に出力する。ただし、出力すべき値は非常に大きくなりうるので、代わりに 1,000,000,007 で割った余りを出力する。 

Sample Input 1

abab
ab

Sample Output 1

3

Sample Input 2

aaaabaaaabaaaabaaaab
aaaaa

Sample Output 2

4368

Sample Input 3

data
structure

Sample Output 3

0



Sample input:
abab
ab


Sample output:
3

Submission status: Wrong Answer

Solution code:
def main():
    MOD = 1000000007
    s,t = input(),input()
    n,m = len(s),len(t)
    dp = [[0 for i in range(m+1)] for j in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        for j in range(m-1,-1,-1):
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= MOD
            if s[i] == t[j]:
                dp[i+1][j+1] += dp[i][j]
                dp[i+1][j+1] %= MOD
    sum = 0
    for i in range(n+1):
        sum += dp[i][m]
    print(sum)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    MOD = 1000000007
    s,t = input(),input()
    n,m = len(s),len(t)
    dp = [[0 for i in range(m+1)] for j in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        for j in range(m-1,-1,-1):
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= MOD
            if s[i] == t[j]:
                dp[i+1][j+1] += dp[i][j]
                dp[i+1][j+1] %= MOD
    sum = 0
    for i in range(n+1):
        sum += dp[i][m]
    print(sum%MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
t = input()
b = input()

MOD = 10**9 + 7

cnts = [0]*(len(b)+1)
cnts[0] = 1

for c in t:
    for i in range(len(b)-1, -1, -1):
        if c == b[i]:
            cnts[i+1] = (cnts[i+1] + cnts[i]) % MOD
print(cnts[-1])

Submission status: Accepted

Solution code:
"""
dp[x][y] ... tのx文字目までで, y文字一致した場合の数
dp[x][y] = dp[x - 1][y] + dp[x - 1][y - 1] * (t[x] == b[y])
"""
MOD = 1000000007
t = input()
b = input()
lent = len(t)
lenb = len(b)
dp = [[0] * (lenb + 1) for _ in range(lent + 1)]
for i in range(lent + 1):
  dp[i][0] = 1

for x in range(1, lent + 1):
  for y in range(1, lenb + 1):
    dp[x][y] = (dp[x - 1][y] + dp[x - 1][y - 1] * (t[x - 1] ==  b[y - 1])) % MOD
print(dp[lent][lenb])

Submission status: Accepted

Solution code:
MOD = 1000000007
t = input()
b = input()
lent = len(t)
lenb = len(b)
dp = [0] * (lenb + 1)
dp[0] = 1
for x in range(1, lent + 1):
  ct = t[x - 1]
  for y in range(lenb, 0, -1):
    if ct == b[y - 1]:
      dp[y] += dp[y - 1]
      dp[y] %= MOD
print(dp[lenb])

Submission status: Accepted

Solution code:

t = input()
b = input()

table = [[0 for i in range(len(t))] for j in range(len(b))]


if len(t) > len(b):

    if t[0] == b[0]:
        table[0][0] = 1
    
    for i in range(1, len(t)):
        if t[i] == b[0]:
            table[0][i] = table[0][i-1] + 1
        else:
            table[0][i] = table[0][i-1]
    
    
    for i in range(1, len(b)):
        
        if b[i] == t[i]:
            table[i][i] = table[i-1][i-1]

        for j in range(i+1, len(t)):
            if b[i] == t[j]:
                table[i][j] = table[i-1][j-1] + table[i][j-1]
            else:
                table[i][j] = table[i][j-1]

    print(table[len(b)-1][len(t)-1] % 1000000007)

elif len(t) == len(b):
    if t == b:
        print(1)
    else:
        print(0)
        
else:
    print(0)