双倍经验：https://www.luogu.com.cn/problem/P3435

实际上就是求每个前缀的；最短非0公共前后缀长度

那么可以先正常求一次前缀函数，然后从前往后维护为只保留最短的。

假设 s[0]~s[i-1] 的最短的都求完了：minNxt[0]~minNxt[i-1]

那么显然 minNxt[i] 要么是 nxt[i] 要么是前 nxt[i] 个字符的 minNxt。

所以：

if (minNxt[nxt[i] - 1] != 0)
    minNxt[i] = minNxt[nxt[i] - 1];
else
    minNxt[i] = nxt[i];

下面的代码复用了 nxt 作为 minNxt。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXL = 1000000;
string t, p;
int nxt[MAXL + 5];
void getNxt(const string &s)
{
    nxt[0] = 0;
    for (int i = 1; i < s.length(); i++)
    {
        int j = nxt[i - 1];
        while (j != 0 && s[j] != s[i])
            j = nxt[j - 1];
        if (s[j] == s[i])
            j++;
        nxt[i] = j;
    }
}
// 把 nxt 改为最短的非0公共前后缀长度
void getMinNxt(const string &s)
{
    for (int i = 1; i < s.length(); i++)
        if (nxt[i] != 0 && nxt[nxt[i] - 1] != 0)
            nxt[i] = nxt[nxt[i] - 1];
}
int k;
string s;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> k;
    cin >> s;
    getNxt(s);
    getMinNxt(s);
    int ans = 0;
    for (int i = 0; i < s.length(); i++)
    {
        // s[0]~s[i] 的长度 - 最小的非0公共前后缀长度
        //= s[0]~s[i] 的最大周期
        if (nxt[i] != 0)
            ans += (i + 1) - nxt[i];
    }
    cout << ans << "\n";
    return 0;
}