Problem:


 
不運なイクタ君は持っていた大事な文字列Tをウィルスによって異なる文字列T'に書き換えられてしまった。そのウィルスがTの１文字を異なる文字に書き換えてしまったことがわかっている。すなわちTとT'はちょうど１文字のみ異なっている。イクタ君はTを復元するために、Tが出現していると思われる文書Sを用意した。Tを復元するための下準備としてSの部分文字列でTと一致している可能性があるものの個数を調べたい。

文字列T'と文書Sが与えられる。
S = a1 a2 a3 . . . a|S|の長さ|T'|の部分文字列ak ak+1 . . . ak+|T'|&minus;1(1 ≤ k ≤ |S| &minus; |T'| + 1)
でT'と比較して1文字だけ異なるものの数を求めよ。

Input

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

S
T'

１行目でSが与えられる。

２行目でT'が与えられる。

S, T'はそれぞれ大文字、小文字のアルファベットのみからなる。

Constraints

入力中の各変数は以下の制約を満たす。

1 ≤ |S| ≤ 300,000

1 ≤ |T'| ≤ |S|

Output

条件を満たす部分文字列の数を1行に出力せよ。

Sample Input 1

abcbcdbc
abc

Output for the Sample Input 1

2

Sの3番目の文字から始まるcbc, Sの6番目の文字から始まるdbcが条件を満たす。

Sample Input 2

aaaaaa
aaaaaa

Output for the Sample Input 2

0

完全に一致する文字列は数えてはならない。

Sample Input 3

baaaaaaaa
b

Output for the Sample Input 3

8



Sample input:
abcbcdbc
abc


Sample output:
2

Submission status: Accepted

Solution code:
import string
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def solve():
    s0 = "^" + string.ascii_uppercase + string.ascii_lowercase
    *S, = map(s0.index, readline().strip()); N = len(S)
    *T, = map(s0.index, readline().strip()); M = len(T)

    base = 59; mod = 10**9 + 9
    pw = [1]*(N+1)
    r = 1
    for i in range(N):
        pw[i+1] = r = r * base % mod

    h0 = [0]*(M+1)
    r = 0
    for i in range(M):
        h0[i+1] = r = (r * base + T[i]) % mod

    h1 = [0]*(N+1)
    r = 0
    for i in range(N):
        h1[i+1] = r = (r * base + S[i]) % mod

    ans = 0
    for i in range(N-M+1):
        left = 0; right = M+1
        while left+1 < right:
            mid = (left + right) >> 1
            if h0[mid] == (h1[mid+i] - h1[i] * pw[mid]) % mod:
                left = mid
            else:
                right = mid
        if left < M:
            if (h0[M] - h0[left+1] * pw[M - (left+1)]) % mod == (h1[M+i] - h1[i+left+1] * pw[M - (left+1)]) % mod:
                ans += 1
    write("%d\n" % ans)
solve()