ADAMATCH - Ada and Nucleobase

Ada the Ladybug is helping her friend who is biologist. He examines DNA. Actually he has a long DNA of one bug, consisting of adenine, cytosine, guanine and thymine and he wants to know whether another bug might be relative to first bug. A bug is relative to another bug if his his DNA has very low Hamming Distance with some substring of the first bug.

Your job is to find the lowest hamming distance between second DNA and any substring of first DNA.

Input

Input contains only two lines: first DNA (s) and second DNA (r).

It is true that 0 < |r| ≤ |s| ≤ 5*105

|s| means length of string s.

All strings contains only A, C, T, and G .

Output

Print minimal Hamming Distance (the number of mismatched nucleobases) of any substring of s and r (the substring MUST have length |r|)

Example Inputs

ACTGACTGACTG
ACCG
AAAAAACCA
AAACA
ACGC
GGG
ACTTTG
TTTGA
ACTGACTGACTG
ACTG

Example Output

1
1
2
3
0

Inputs explanation

ACTGACTGACTG
AAAAAACCA
ACGC
ACTTTG
ACTGACTGACTG 

Added by:Morass
Date:2017-02-09
Time limit:6.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU

hide comments
2022-09-01 20:38:24 Mitch Schwartz
@bashkort: I'm not well acquainted with the new features they would introduce, but C++17 and C++20 sound like reasonable requests to me. I recommend sending an email to contact@spoj.com (this email address is listed on the About page) to ask admins whether they would be willing to add an updated C++.
2022-09-01 17:13:24
I hate spoj.com, always get complitation error qwq
Why can't you add c++17???
2022-07-25 12:41:32
can any body taught me how fft work?
please mail me on rohitkumpan01@gmail.com

Last edit: 2022-07-25 12:42:00
2022-04-28 07:54:31
@[Lakshman]
yes, I was able to get my java accepted
2021-06-01 07:48:17 [Lakshman]
Is there any chance of getting AC with Java?
2020-01-08 14:09:29
FFT!
2019-12-10 17:51:00
Nice problem to use fft.
2017-02-10 03:37:58
@Min_25: Sorry for that :'( (sadly I have low "overlook" over SPOJ database problems )
2017-02-10 03:30:34 Min_25
Almost the same problem as http://www.spoj.com/problems/MAXMATCH/.
2017-02-10 01:35:12
@[Rampage] Blue.Mary: Thank you for first-solving (==> testing). Have nice day!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.