No.2626 Similar But Different Name
タグ : / 解いたユーザー数 64
作問者 : 👑
Magentor
Problem Statement
For strings $X, Y$ consisting of uppercase and lowercase English letters, if both of the following conditions are satisfied, those $2$ strings are said to be similar but different strings of each other.
- $X$ and $Y$ match when the distinction between uppercase and lowercase letters is ignored.
- The number of positions where $X$ and $Y$ differ in case is at least $1$ and at most $K$.
For example, when $K=2$, ABC and aBc satisfy both of the conditions above, so they are similar but different strings of each other. On the other hand, the following examples are not similar but different strings of each other.
ABCandBCD(they do not match even when the distinction between uppercase and lowercase letters is ignored)ABCandABC(the number of positions that differ in case is $0$)ABCandabc(the number of positions that differ in case is $3$)
You are given a string $S$ of length $N$ and a string $T$ of length $M$, both consisting of uppercase and lowercase English letters.
Find the number of (contiguous) substrings of $S$ that are similar but different strings of $T$.
Here, two substrings are treated as different if they are taken from different positions, even if they are equal as strings. (Added 2024/2/9 21:31)
Constraints
- $N, M, K$ are integers.
- $1 \leq K \leq M \leq N \leq 5 \times 10^5$
- $S$ is a string of length $N$ consisting of uppercase and lowercase English letters.
- $T$ is a string of length $M$ consisting of uppercase and lowercase English letters.
Input
The input is given from standard input in the following format.
$N$ $M$ $K$ $S$ $T$
Output
Output the answer.
Sample
Sample 1
Input
8 2 1 aiaIAiAI AI
Output
2
aI and Ai are similar but different strings of AI, but ai and AI are not similar but different strings of AI.
Sample 2
Input
7 3 2 aaaaaaa AAA
Output
0
No substring of aaaaaaa is a similar but different string of AAA.
Sample 3
Input
15 2 1 DXDXGdXdXgDxDxG Dx
Output
2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。