满分代码,dp优化

#include <bits/stdc++.h>
using namespace std;

// 说明：计算所有前缀的最大周期长度之和
// 关键：线性求 π 表，并用 DP 得到“每个前缀的最短正 border” mn[i]
// 最大周期 = 前缀长度 - 最短正 border

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int k;
    string s;
    if (!(cin >> k)) return 0;
    cin >> s;
    int n = (int)s.size();

    vector<int> pi(n, 0);  // 前缀函数 π 表
    vector<int> mn(n, 0);  // 每个前缀的“最短正 border”长度
    long long ans = 0;

    // i=0 的前缀：pi[0]=0，mn[0]=0，最大周期为 0
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        // 失配则沿失败链回退
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) ++j;
        pi[i] = j;

        // 线性 DP：最短正 border
        int b = pi[i];
        if (b == 0) {
            mn[i] = 0;
        } else {
            int t = mn[b - 1];
            mn[i] = (t == 0 ? b : t);
        }

        // 累加该前缀的最大周期
        if (mn[i] > 0) ans += (long long)(i + 1 - mn[i]);
        // 否则无周期，加 0
    }

    cout << ans << '\n';
    return 0;
}

大概60分代码:

#include <bits/stdc++.h>
using namespace std;

// 计算前缀函数 π 表：pi[i] = s[0..i] 的最长真前后缀长度
vector<int> kmp_pi(const string &s) {
    int n = (int)s.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        // 失配则沿失败链回退
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) ++j;   // 可延长一位
        pi[i] = j;
    }
    return pi;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int k; 
    string s;
    if (!(cin >> k)) return 0;
    cin >> s;

    vector<int> pi = kmp_pi(s);
    long long sum = 0;

    // 枚举每个前缀 s[0..i]，长度 n=i+1
    for (int i = 0; i < k; ++i) {
        int n = i + 1;
        int b = pi[i];         // 最长 border
        if (b == 0) {
            // 无正 border，最大周期为 0
            // sum += 0;
            continue;
        }
        // 顺链找到“最短正 border”
        // 即：继续跳，直到下一跳为 0 为止
        while (pi[b - 1] != 0) b = pi[b - 1];

        int p = n - b;         // 最大周期长度
        sum += p;
    }

    cout << sum << '\n';
    return 0;
}