Maximum Questions

题意翻译

给定长度为 $n$ 的字符串$S$，$S$仅由```'a','b','?'```组成，你可以将```'?'```当做```'a'```或```b```使用。 再给出长度为 $m$ 的形如 ```ababab...``` 的字符串$T$，$T$是由```'a','b'```交替组成的。显然，只要知道长度 $m$，你就会知道$T$是什么样子的。 求至少使用多少个```'?'```, 使得$S$能匹配最多的不相交的$T$。 输入共三行，包括$n,S,m$。 输出最少使用的```'?'```数。 数据范围：$1\leqslant n,m\leqslant10^5$。

题目描述

Vasya wrote down two strings $ s $ of length $ n $ and $ t $ of length $ m $ consisting of small English letters 'a' and 'b'. What is more, he knows that string $ t $ has a form "abab...", namely there are letters 'a' on odd positions and letters 'b' on even positions. Suddenly in the morning, Vasya found that somebody spoiled his string. Some letters of the string $ s $ were replaced by character '?'. Let's call a sequence of positions $ i,i+1,...,i+m-1 $ as occurrence of string $ t $ in $ s $ , if $ 1<=i<=n-m+1 $ and $ t_{1}=s_{i},t_{2}=s_{i+1},...,t_{m}=s_{i+m-1} $ . The boy defines the beauty of the string $ s $ as maximum number of disjoint occurrences of string $ t $ in $ s $ . Vasya can replace some letters '?' with 'a' or 'b' (letters on different positions can be replaced with different letter). Vasya wants to make some replacements in such a way that beauty of string $ s $ is maximum possible. From all such options, he wants to choose one with the minimum number of replacements. Find the number of replacements he should make.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1<=n<=10^{5} $ ) — the length of $ s $ . The second line contains the string $ s $ of length $ n $ . It contains small English letters 'a', 'b' and characters '?' only. The third line contains a single integer $ m $ ( $ 1<=m<=10^{5} $ ) — the length of $ t $ . The string $ t $ contains letters 'a' on odd positions and 'b' on even positions.

输出格式

Print the only integer — the minimum number of replacements Vasya has to perform to make the beauty of string $ s $ the maximum possible.

输入输出样例

输入样例 #1

5
bb?a?
1

输出样例 #1

2

输入样例 #2

9
ab??ab???
3

输出样例 #2

2

说明

In the first sample string $ t $ has a form 'a'. The only optimal option is to replace all characters '?' by 'a'. In the second sample using two replacements we can make string equal to "aba?aba??". It is impossible to get more than two occurrences.

题意翻译

给定长度为 $n$ 的字符串$S$，$S$仅由```'a','b','?'```组成，你可以将```'?'```当做```'a'```或```b```使用。 再给出长度为 $m$ 的形如 ```ababab...``` 的字符串$T$，$T$是由```'a','b'```交替组成的。显然，只要知道长度 $m$，你就会知道$T$是什么样子的。 求至少使用多少个```'?'```, 使得$S$能匹配最多的不相交的$T$。 输入共三行，包括$n,S,m$。 输出最少使用的```'?'```数。 数据范围：$1\leqslant n,m\leqslant10^5$。