C++14(g++5.4) 解法, 执行用时: 20ms, 内存消耗: 5268K, 提交时间: 2019-12-08 22:36:06

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

int main() {
  ios_base::sync_with_stdio(false);
  int n; cin >> n;
  string S; cin >> S; S.append("#");
  vector<int> next(n+1, -1);
  for (int i = 0, j = -1; i < n; next[++i] = ++j) {
    while (j != -1 && S[i] != S[j]) j = next[j];
  }
  long long tot = 0;
  for (int i = 0; i < n; i++) {
    int j = i+1;
    while (next[next[j]] != -1) j = next[j];
    if (next[next[i+1]] != -1) next[i+1] = j;
    // cout << i << " " << j << endl;
    if (j != 0) tot += i + 1 - j;
  }
  cout << tot << endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 15ms, 内存消耗: 8940K, 提交时间: 2020-03-05 13:11:17

#include<cstdio>
char str[1000010];
int next[1000010],cnt[1000010];
int main()
{
	int n,i=0,j=-1;
	long long ans=0;
	scanf("%d%s",&n,str);
	next[0]=-1;
	while(i<n)
	{
		while(~j&&str[j]!=str[i]) j=next[j];
		i++,j++,next[i]=j;
	}
	for(i=1;i<=n;i++)
	{
		if(next[i]!=0) cnt[i]=cnt[next[i]];
		else cnt[i]=i;
		ans+=i-cnt[i];
	}
	printf("%lld\n",ans);
	return 0;
}