問題一覧 > 通常問題

No.2626 Similar But Different Name

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 64
作問者 : 👑 AngrySadEight / テスター : Magentor zeta7532
お気に入りにしたユーザー ProblemId : 10497 / 自分の提出
問題文最終更新日: 2024-02-09 21:32:03
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 417 (順位表) の他の問題:

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.

  • ABC and BCD (they do not match even when the distinction between uppercase and lowercase letters is ignored)
  • ABC and ABC (the number of positions that differ in case is $0$)
  • ABC and abc (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もしくは右上の雲マークをクリックしてアカウントを作成してください。