CodeForces527D. Fuzzy Search

Leonid works for a small and promising start-up that works on decoding the human genome. His duties include solving complex problems of finding certain patterns in long strings consisting of letters 'A', 'T', 'G' and 'C'.

Let's consider the following scenario. There is a fragment of a human DNA chain, recorded as a string S. To analyze the fragment, you need to find all occurrences of string T in a string S. However, the matter is complicated by the fact that the original chain fragment could contain minor mutations, which, however, complicate the task of finding a fragment. Leonid proposed the following approach to solve this problem.

Let's write down integer k ≥ 0 — the error threshold. We will say that string T occurs in string S on position i (1 ≤ i ≤ |S| - |T| + 1), if after putting string T along with this position, each character of string T corresponds to the some character of the same value in string S at the distance of at most k. More formally, for any j (1 ≤ j ≤ |T|) there must exist such p (1 ≤ p ≤ |S|), that |(i + j - 1) - p| ≤ k and S[p] = T[j].

For example, corresponding to the given definition, string "ACAT" occurs in string "AGCAATTCAT" in positions 2, 3 and 6.

Note that at k = 0 the given definition transforms to a simple definition of the occurrence of a string in a string.

Help Leonid by calculating in how many positions the given string T occurs in the given string S with the given error threshold.

Input

The first line contains three integers |S|, |T|, k (1 ≤ |T| ≤ |S| ≤ 200 000, 0 ≤ k ≤ 200 000) — the lengths of strings S and T and the error threshold.

The second line contains string S.

The third line contains string T.

Both strings consist only of uppercase letters 'A', 'T', 'G' and 'C'.

Output

Print a single number — the number of occurrences of T in S with the error threshold k by the given definition.

Examples

input

10 4 1
AGCAATTCAT
ACAT

output

Note

If you happen to know about the structure of the human genome a little more than the author of the problem, and you are not impressed with Leonid's original approach, do not take everything described above seriously.

Solution

只要A串中[i-k,i+k]范围内有字符X，就认为i位置可以匹配字符X。

问有多少位置可以匹配目标串B

生成函数 FFT

注意到只有四种字符，那么可以暴力分别处理这四种字符。

对于每种字符，在A串中扫描出可以匹配它的所有位置，标记为1，再将B串反转，将B串上对应字符的位置也标记为1，卷积即可得到该种字符的匹配情况。

做四遍卷积就可以愉快出解了。

 1 /*by SilverN*/
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 #include<vector>
 8 #define LL long long
 9 using namespace std;
10 const double pi=acos(-1.0);
11 const int mxn=400010;
12 int read(){
13     int x=0,f=1;char ch=getchar();
14     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
15     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
16     return x*f;
17 }
18 struct com{
19     double x,y;
20     com operator + (const com &b){return (com){x+b.x,y+b.y};}
21     com operator - (const com &b){return (com){x-b.x,y-b.y};}
22     com operator * (const com &b){return (com){x*b.x-y*b.y,x*b.y+y*b.x};}
23     com operator / (double v){return (com){x/v,y/v};}
24 }a[mxn<<1],b[mxn<<1];
25 int N,len;
26 int rev[mxn<<1];
27 void FFT(com *a,int flag){
28     for(int i=0;i<N;i++)
29         if(i<rev[i])swap(a[i],a[rev[i]]);
30     for(int i=1;i<N;i<<=1){
31         com wn=(com){cos(pi/i),flag*sin(pi/i)};
32         int p=i<<1;
33         for(int j=0;j<N;j+=p){
34             com w=(com){1,0};
35             for(int k=0;k<i;k++,w=w*wn){
36                 com x=a[j+k],y=w*a[j+k+i];
37                 a[j+k]=x+y;
38                 a[j+k+i]=x-y;
39             }
40         }
41     }
42     if(flag==-1)for(int i=0;i<N;i++) a[i].x/=N;
43     return;
44 }
45 char s[mxn],c[mxn];
46 int S,T,K;
47 LL ans[mxn<<1];
48 int hd,tl,ct;
49 void solve(char tp){
50     memset(a,0,sizeof a);
51     memset(b,0,sizeof b);
52     hd=0;tl=-1;ct=0;
53     int i,j;
54     for(i=0;i<S;i++){
55         while(i-hd>K){if(s[hd]==tp)ct--;hd++;}
56         while(tl-i+1<=K && tl<S){tl++;if(s[tl]==tp)ct++;}
57         if(ct>0) a[i].x=1;
58     }
59     for(i=0;i<T;i++)
60         if(c[i]==tp) b[i].x=1;
61     FFT(a,1);FFT(b,1);
62     for(i=0;i<N;i++) a[i]=a[i]*b[i];
63     FFT(a,-1);
64     for(i=0;i<N;i++)ans[i]+=(LL)(a[i].x+0.5);
65 
66     return;
67 }
68 int main(){
69     int i,j;
70     S=read();T=read();K=read();
71     scanf("%s",s);scanf("%s",c);
72     int m=S+T;
73     for(N=1,len=0;N<=m;N<<=1)len++;
74     for(i=0;i<N;i++)
75         rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));
76     reverse(c,c+T);
77     solve('A');
78     solve('G');
79     solve('C');
80     solve('T');
81     int res=0;
82     for(i=0;i<N;i++){
83         if(ans[i]==T)res++;
84 //        printf("%lld
",ans[i]);
85     }
86     printf("%d
",res);
87     return 0;
88 }