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*10^{5}
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
hide comments
Mitch Schwartz:
20220901 20:38:24
@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++. 

bashkort:
20220901 17:13:24
I hate spoj.com, always get complitation error qwq


rohit9123:
20220725 12:41:32
can any body taught me how fft work?


bucketofnubs:
20220428 07:54:31
@[Lakshman]


[Lakshman]:
20210601 07:48:17
Is there any chance of getting AC with Java? 

heromayank2:
20200108 14:09:29
FFT! 

zer0_h6cks:
20191210 17:51:00
Nice problem to use fft. 

morass:
20170210 03:37:58
@Min_25: Sorry for that :'( (sadly I have low "overlook" over SPOJ database problems ) 

Min_25:
20170210 03:30:34
Almost the same problem as http://www.spoj.com/problems/MAXMATCH/. 

morass:
20170210 01:35:12
@[Rampage] Blue.Mary: Thank you for firstsolving (==> testing). Have nice day! 
Added by:  Morass 
Date:  20170209 
Time limit:  6.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 