Gene Sequence Matching

At Garyton University's Institute of Biological Research, a gene sequence $S$ was discovered that determines whether a person likes lotus root. An individual carrying this gene exhibits a fondness for lotus root; however, researchers found that any modification of at most $3$ nucleotides in $S$ still results in the lotus root preference. Given a person's DNA sequence $S_0$ (which displays the lotus root liking trait), count the number of contiguous substrings of $S_0$ that can be transformed into $S$ by modifying at most $3$ nucleotides.

The mathematical condition is: For each contiguous substring $T$ of $S_0$ with $|T|=|S|$, if the Hamming distance between $T$ and $S$ satisfies $$d_H(T,S) \leq 3,$$ then $T$ is a candidate gene location.

inputFormat

The input consists of two lines:

• The first line contains the DNA sequence $S_0$ of a person displaying the trait.
• The second line contains the gene sequence $S$.

It is guaranteed that $|S_0| \geq |S|$, and both sequences consist only of the characters A, C, G, and T.

outputFormat

Output a single integer representing the count of contiguous substrings of $S_0$ (of length equal to $|S|$) that can be transformed into $S$ by modifying at most $3$ nucleotides (i.e. having a Hamming distance of at most $3$ from $S$).

sample

ACGT
ACG

2