请问以下代码的时间复杂度是多少？

#include <bits/stdc++.h>
#define int long long
#define _ (int)(2e6 + 4)
using namespace std;

int n, ans;
int pre[_], w[_];
char s[_];

signed main()
{
  cin >> n;
  for (int i(1); i <= n; i ++) cin >> s[i];
  for (int i(1); i <= n; i ++) {
    int p(i);
    while (p) {
      if (s[p - 1] == s[i]) {
        pre[i] = p - 1;
        break;
      } p = pre[p - 1];
    } w[pre[i]] ++;
  }
  for (int i(n); i >= 1; i --) {
    ans += w[i];
    w[pre[i - 1]] += w[i];
  }
  cout << ans;

  return 0;
}