思路与算法

构造后缀自动机。每个非初始状态v表示的不同子串长度恰是(len[link[v]],len[v]]，在该区间内每种长度恰有一个不同子串。遍历状态，若len[link[v]]<m≤len[v]就贡献1，累加得到答案。

正确性说明

SAM将具有同一结束位置集合的子串归为一个状态，这些子串恰为一条后缀链，对应连续长度区间。任意不同子串唯一属于一个状态，固定长度m在覆盖该长度的状态中各出现一次，因此计数既不遗漏也不重复。克隆状态分裂转移时保留标准SAM不变量，维护这些区间。

复杂度

固定26字母表，构造O(26n)时间、O(26n)空间，遍历O(n)；节点数组初始化和克隆复制26项均计入。n≤20万，预留2n节点防止反复扩容。没有哈希碰撞问题。

易错点

求的是不同子串个数，不是出现次数n-m+1。字符重复会合并等价子串。m=1时答案是不同字母数，m=n时必为1。独立答案用原始长度m字符串切片放入Python集合，包含20万规模。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct State {
    int next[26], link = -1, len = 0;
    State() {
        fill(next, next + 26, -1);
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    string s;
    cin >> n >> m >> s;
    vector<State> st;
    st.reserve(2 * n);
    st.emplace_back();
    int last = 0;
    for (char ch : s) {
        int c = ch - 'a', cur = st.size();
        st.emplace_back();
        st[cur].len = st[last].len + 1;
        int p = last;
        while (p >= 0 && st[p].next[c] < 0) {
            st[p].next[c] = cur;
            p = st[p].link;
        }
        if (p < 0)
            st[cur].link = 0;
        else {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len)
                st[cur].link = q;
            else {
                int clone = st.size();
                st.push_back(st[q]);
                st[clone].len = st[p].len + 1;
                while (p >= 0 && st[p].next[c] == q) {
                    st[p].next[c] = clone;
                    p = st[p].link;
                }
                st[q].link = st[cur].link = clone;
            }
        }
        last = cur;
    }
    int ans = 0;
    for (size_t i = 1; i < st.size(); ++i)
        ans += st[st[i].link].len < m && m <= st[i].len;
    cout << ans << '\n';
}