给定一个由小写英文字母组成的字符串，其长度为 n。我们需要统计其中有多少个长度为 m 的不同子串。这个数量将作为该字符串的评分。

输入格式

第一行包含两个整数 n 和 m，表示字符串的长度和需要统计的子串长度。
1 ≤ m ≤ n ≤ 200000
第二行包含一个长度为 n 的只包含小写字母的字符串。

输出格式

一行一个整数，表示字符串的评分。

示例

输入

5 3
aaaab
    

输出

2
    

样例解释： 长度为 3 的子串有 3 个，分别是 "aaa"、"aaa" 和 "aab"。其中只有 2 个是不同的。

实现思路

这个问题可以通过字符串哈希来解决。我们可以为每个长度为 m 的子串计算一个哈希值，然后统计不同哈希值的数量。为了避免哈希冲突，通常会使用双哈希或多哈希技术。

本例中，考虑到数据可能较大，我们采用了三哈希的方法来进一步降低冲突的概率。我们将使用三个不同的质数作为模数和三个不同的基数来计算哈希值。

代码实现

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>

long long n, m;
std::string s;

// 定义三个哈希参数
const int MOD1 = 19260819;
const int MOD2 = 19260809;
const int MOD3 = 19260719;
const long long BASE1 = 193;
const long long BASE2 = 137;
const long long BASE3 = 107;

std::vector<long long> pow1, pow2, pow3;
std::vector<long long> hash1, hash2, hash3;

// 初始化哈希所需的幂次表和前缀哈希表
void precompute_hashes() {
    pow1.resize(n + 1);
    pow2.resize(n + 1);
    pow3.resize(n + 1);
    hash1.resize(n + 1, 0);
    hash2.resize(n + 1, 0);
    hash3.resize(n + 1, 0);

    pow1[0] = 1;
    pow2[0] = 1;
    pow3[0] = 1;

    for (int i = 1; i <= n; ++i) {
        pow1[i] = (pow1[i - 1] * BASE1) % MOD1;
        pow2[i] = (pow2[i - 1] * BASE2) % MOD2;
        pow3[i] = (pow3[i - 1] * BASE3) % MOD3;

        hash1[i] = (hash1[i - 1] * BASE1 + (s[i - 1] - 'a' + 1)) % MOD1;
        hash2[i] = (hash2[i - 1] * BASE2 + (s[i - 1] - 'a' + 1)) % MOD2;
        hash3[i] = (hash3[i - 1] * BASE3 + (s[i - 1] - 'a' + 1)) % MOD3;
    }
}

// 获取子串的哈希值
std::tuple<long long, long long, long long> get_substring_hash(int start_idx, int len) {
    long long h1 = (hash1[start_idx + len - 1] - (hash1[start_idx - 1] * pow1[len]) % MOD1 + MOD1) % MOD1;
    long long h2 = (hash2[start_idx + len - 1] - (hash2[start_idx - 1] * pow2[len]) % MOD2 + MOD2) % MOD2;
    long long h3 = (hash3[start_idx + len - 1] - (hash3[start_idx - 1] * pow3[len]) % MOD3 + MOD3) % MOD3;
    return {h1, h2, h3};
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> n >> m >> s;

    precompute_hashes();

    std::unordered_set<long long> distinct_hashes1;
    std::unordered_set<long long> distinct_hashes2;
    std::unordered_set<long long> distinct_hashes3;

    int distinct_count = 0;

    for (int i = 1; i <= n - m + 1; ++i) {
        auto [h1, h2, h3] = get_substring_hash(i, m);

        bool new_hash = false;
        if (distinct_hashes1.find(h1) == distinct_hashes1.end()) {
            distinct_hashes1.insert(h1);
            distinct_hashes2.insert(h2);
            distinct_hashes3.insert(h3);
            distinct_count++;
            new_hash = true;
        } else {
            // 检查是否是真正的相同哈希值，如果不是，则也算作新的
            if (distinct_hashes2.find(h2) == distinct_hashes2.end() || distinct_hashes3.find(h3) == distinct_hashes3.end()) {
                // 尽管第一个哈希值相同，但另外两个不同，这可能意味着冲突或需要更严格的判断
                // 在这个实现中，我们假设如果第一个哈希值不同，那么就一定是一个新的子串
                // 如果第一个哈希值相同，我们仍然需要检查其他哈希值
                // 但更严谨的做法是，当一个子串的三个哈希值组合都没有出现过时，才算新的
            }
        }
    }

    // 更为严谨的去重逻辑，使用一个 set 来存储三元组哈希值
    std::set<std::tuple<long long, long long, long long>> unique_hashes;
    for (int i = 1; i <= n - m + 1; ++i) {
        unique_hashes.insert(get_substring_hash(i, m));
    }

    std::cout << unique_hashes.size() << std::endl;

    return 0;
}