题意

给你两个字符串$SS$和$TT$，让你求$SS$中有多少个子串和$TT$是$kk$匹配的，$kk$匹配的概念就是两个字符串存在长度为$kk$的子串是相同的

思路

我们计算以第$ii$开头有多少个子串是和$TT$为$kk$匹配的，然后求个和就是最终答案了

那么假设要以某位开头的话，我们可能要找到第一次匹配的地方，然后这个位置后面的字母任意取就好

比如$n=5n\; =\; 5$， $k=3k\; =\; 3$ $S=ababaS\; =\; ababa$，$T=abaT\; =\; aba$ 那么我们可以用kmp求出$SS$中所有和$TT$匹配的位置

ababa

vxvxx

v表示匹配，x表示不匹配

那么可以计算出每一位到它第一次匹配的位是哪个

ababa

355-1-1

-1表示从这个位往后的字符串都没有匹配到$TT$的 那么比如以第一位为开头的话，答案就是5 - 3 + 1 = 3，也就是aba， abab, ababa，就是从3开始往后都可以随便取

代码

/**
 *    author: andif
 *    created: 22.06.2023 21:55:42
**/
#include<bits/stdc++.h>
using namespace std;

#define de(x) cerr << #x << " = " << x << endl
#define dd(x) cerr << #x << " = " << x << " "
#define rep(i, a, b) for(int i = a; i < b; ++i)
#define per(i, a, b) for(int i = a; i > b; --i)
#define mt(a, b) memset(a, b, sizeof(a))
#define sz(a) (int)a.size()
#define fi first
#define se second
#define qc ios_base::sync_with_stdio(0);cin.tie(0)
#define eb emplace_back
#define all(a) a.begin(), a.end()
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pdd = pair<db, db>;
using pll = pair<ll, ll>;
using vi = vector<int>;
const db eps = 1e-9;

vi get_next(const string& s) {
    int n = sz(s) - 1;
    vi next(n + 1, 0);
    rep(i, 2, n + 1) {
        int j = i - 1;
        while(j && s[i] != s[next[j] + 1]) j = next[j];
        if (j) next[i] = next[j] + 1;
    }
    return next;
}

vi match(const string& s, const string& t, const vi& next) {
    vi match_pos;
    int n = sz(s) - 1, m = sz(t) - 1;
    int i = 1, j = 1;
    while(i <= n) {
        if (s[i] == t[j]) {
            if (j == m) {
                match_pos.eb(i - m + 1);
                j = next[j];
            }
            i++; j++;
        } else if (j == 1) {
            i++;
        } else {
            j = next[j - 1] + 1;
        }
    }
    return match_pos;
}

int main() {
    qc;
    int n, k; cin >> n >> k;
    string s, t; cin >> s >> t;
    s = '#' + s;
    t = '#' + t;
    ll ans = 0;
    vi next = get_next(t);
    vi match_pos = match(s, t, next);
    vi b(n + 1);
    fill(all(b), -1);
    int i = 1;
    rep(j, 0, sz(match_pos)) {
        while(i <= match_pos[j]) {
            b[i++] = match_pos[j];
        }
    }
    // rep(i, 1, n + 1) dd(i), de(b[i]);
    rep(i, 1, n + 1) {
        if (b[i] == -1) break;
        b[i] = b[i] + k - 1;
        ans = ans + n - b[i] + 1;
    }
    cout << ans << '\n';
    return 0;
}