P3435

P3435

• 设 \(Q = a[1, i]\)，左端绿色虚线终点为 j

• 则 \(a[1, j] == a[i + 1, n]\)，因为他们位于 Q 的相同位置

• 联想到 kmp 的 next 数组

  • \(len_Q = n - next[j]\)
  • 只要找到最小的且非0的 \(next[j]\) 就可以最大化 \(len_Q\)

• 类似失配时的操作，递归找 j 对应的最小 next

• 注意：next 递归时要做记忆化操作，否则会重复同样的操作，时间复杂度变大

# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N = (int)1e6 + 10;

int n;
int nxt[N];
char s[N];

void Get_nxt(){
	int j = 0;
	for(int i = 1; i < n; i++){
		while(j && s[i] != s[j]){
			j = nxt[j - 1];
		}
		if(s[i] == s[j]){
			j++;
		}
		nxt[i] = j;
	}
}

void Work(){
	int j = 1, ans = 0;
	for(int i = 1; i <= n; i++){
		j = i;
		while(nxt[j - 1]){
			j = nxt[j - 1];
		}
		if(nxt[i - 1] != 0){	// 记忆化
			nxt[i - 1] = j;
		}
		ans += i - j;  
	}
	cout << ans << "\n";
}

signed main(){
//	freopen("1.in", "r", stdin);
	cin >> n >> s;
	Get_nxt();
	Work();
}