Matching Pairs
Let X and Y be two unempty strings over unempty alphabet A and let K be a non-negative integer.
We say that (X, Y) is a K-pair if Y can be obtained from X by changing some characters in X on exactly K different positions.
We say that (X, Y) is a K-reduced pair if Y can be obtained from X by removing a substring of length K from X.
Let S be a string. Let S1 and S2 be two unempty substrings of S. Let L be a positive integer, let K be a non-negative integer, both not bigger than the length of S.
We say that S1 and S2 are a (L,K)-matching pair if all following conditions hold.
1. The length of S1 is L, the length of S2 is L or L− K.
2. Substrings S1 and S2 do not overlap, that is, no position in S is simultaneously part of S1 and S2.
3. The pair (S1, S2) is a K-pair or a K-reduced pair.
We say that two (L, K)-matching pairs (S1, S2) and (T1, T2) are different if one of them is a K-pair and the other is a K-reduced pair.
When two (L, K)-matching pairs (S1, S2) and (T1, T2) are both a K-pair, we say that (S1, S2) and (T1, T2) are different if the set of all positions in S occupied by (S1, S2) differs from the set of all positions in S occupied by (T1, T2).
When two (L, K)-matching pairs (S1, S2) and (T1, T2) are both a K-reduced pair, we say that (S1, S2) and (T1, T2) are different if the set of all positions in S occupied by S1 differs from the set of all positions in S occupied by T1 or the set of all positions in S occupied by S2 differs from the set of all
positions in S occupied by T2.
Note that two different (L, K)-matching pairs might sometimes contain identical sequences of charaters. This fact is illustrated in Example 2 below.
The task
You are given the alphabet A, the string S over A and two integers L and K. Find the number of different (L, K)-matching pairs in S.
Input
The input contains two text lines. The first line contains three integers A, L, K. The second line contains a string S over the the alphabet consisting of first A lowercase letters of English alphabet. There are no blanks or spaces on the second line.
It holds, 1 ≤ A ≤ 26, 0 ≤ K < L ≤ 500, L < |S| ≤ 2 000 .
Output
The output contains one text line with one integer representing the number of (L, K)-matching pairs in S.
Example 1
Input
8 5 3
hhgccchggbcbfbaddeca
Output
9
Comment
The (5, 3)-matching pairs in the input string are given below, the positions of the respective substrings in the input string are included.
(hhgcc) (chggb) [ 0 -- 4] [ 5 -- 9]
(hgccc) (ggbcb) [ 1 -- 5] [ 7 -- 11]
(gccch) (ggbcb) [ 2 -- 6] [ 7 -- 11]
(gccch) (gbcbf) [ 2 -- 6] [ 8 -- 12]
(hgccc) (hg) [ 1 -- 5] [ 6 -- 7]
(ccchg) (hg) [ 3 -- 7] [ 1 -- 2]
(chggb) (cb) [ 5 -- 9] [10 -- 11]
(hggbc) (hg) [ 6 -- 10] [ 1 -- 2]
(cbfba) (ca) [10 -- 14] [18 -- 19]
Example 2
Input
7 3 0
cabdcabecabfcabgcab
Output
10
Comment
All 10 (3,0)- matching pairs contain the same sequence 'cab' in their respective substrings.
Example 3
Input
3 7 2
abbaccbbbacbccaccacbbccbbbcabbcccababcbb
Output
24
Comment
The (7, 2)-matching pairs in the input string are given below, the positions of the respective substrings in the input string are included.
(abbaccb, acbbccb) [ 0 -- 6] [17 -- 23]
(abbaccb, abbccca) [ 0 -- 6] [27 -- 33]
(bbaccbb, cbbccbb) [ 1 -- 7] [18 -- 24]
(bbaccbb, bbccbbb) [ 1 -- 7] [19 -- 25]
(bbaccbb, bbbcabb) [ 1 -- 7] [23 -- 29]
(bbaccbb, bbcccab) [ 1 -- 7] [28 -- 34]
(bbaccbb, ababcbb) [ 1 -- 7] [33 -- 39]
(accbbba, bccbbbc) [ 3 -- 9] [20 -- 26]
(ccbbbac, ccbbbca) [ 4 -- 10] [21 -- 27]
(cbbbacb, cbbbcab) [ 5 -- 11] [22 -- 28]
(bbbacbc, bbcabbc) [ 6 -- 12] [24 -- 30]
(bbacbcc, bcabbcc) [ 7 -- 13] [25 -- 31]
(ccacbbc, ccababc) [15 -- 21] [31 -- 37]
(cacbbcc, cabbccc) [16 -- 22] [26 -- 32]
(bbccbbb, bbcccab) [19 -- 25] [28 -- 34]
(bbaccbb, bccbb) [ 1 -- 7] [20 -- 24]
(baccbbb, ccbbb) [ 2 -- 8] [21 -- 25]
(ccbbbac, ccbbb) [ 4 -- 10] [21 -- 25]
(bbacbcc, bbacc) [ 7 -- 13] [ 1 -- 5]
(bccacca, bccca) [11 -- 17] [29 -- 33]
(accacbb, accbb) [14 -- 20] [ 3 -- 7]
(bbccbbb, ccbbb) [19 -- 25] [ 4 -- 8]
(ccbbbca, ccbbb) [21 -- 27] [ 4 -- 8]
(bbcccab, bbccb) [28 -- 34] [19 -- 23]
Public data
The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set