请问这题Z函数怎么写啊qwq，只有80pts

维护了一个pos[x]，表示s[1:x]中距离x位最近的z[p]不为零的p，答案就是统计一下pos[i]-1.

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define vec vector
#define pb push_back
#define SZ(T) ((int)T.size())
#define all(T) T.begin(), T.end()
#define lp (p<<1)
#define rp (p<<1|1)
#define P(T) pair<T, T>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef double db;
mt19937_64 rnd(time(0));
// head
const int N = 1000010;
int pos[N];

vector<int> Z_algorithm(string s) {
  int n = SZ(s);
  s = "#" + s;
  int L = 1, R = 0;
  vector<int> z(n+1, 0);
  z[1] = 0;
  int px = 0;
  for (int i = 2; i <= n; i++) {
    if (i > R)
      z[i] = 0;
    else
      z[i] = min(z[i - L + 1], R - i + 1);

    while (i + z[i] <= n && s[1 + z[i]] == s[i + z[i]])
      ++z[i];
    if (z[i]) pos[i] = max(pos[i], i - 1); // i有前缀，就加上i-1
    else if (px + z[px] - 1 >= i) pos[i] = max(pos[i], px - 1);//没有前缀，那么就统计上一次的i-1

    if (i + z[i] - 1 > R)
      L = i, R = i + z[i] - 1, px = i;
    else if (i + z[i] - 1 == R)
      px = i; // 贪心一下，应该是对的叭???
  }
  return z;
}

void solve(int CaseT) {
  int n;
  string s;
  cin >> n >> s;
  auto z = Z_algorithm(s);
  ll ans = 0;
  for (int i = 1; i <= n; i++) {
    ans += pos[i];
  }
  cout << ans << '\n';
}