[POI2006]OKR-Periods of Words 题解

/**
 * @Author: Mingyu Li
 * @Date:   2019-03-16T23:00:02+08:00
 * @Email:  class11limingyu@126.com
 * @Filename: P3435.cpp
 * @Last modified by:   Mingyu Li
 * @Last modified time: 2019-03-16T23:10:37+08:00
 */

#include <bits/stdc++.h>
#define Go(i , x , y) for(register int i = x; i <= y; i++)
#define God(i , y , x) for(register int i = y; i >= x; i--)
typedef long long LL;
template < typename T > void sc(T& t) {
  char c = getchar(); T x = 1; t = 0; while(!isdigit(c)) {if(c == '-') x = -1; c = getchar();}
  while(isdigit(c)) t = t * 10 + c - '0' , c = getchar();t *= x;
}
template < typename T , typename... Args > void sc(T& t , Args&... args) {sc(t); sc(args...);}

const int N = 1000000 + 10;
int next[N] , n;
char c[N];
int main() {
  sc(n);scanf("%s" , (c + 1));
  next[1] = 0;
  Go(i , 2 , n) {
    int j = next[i-1];
    while(j && c[i] != c[j + 1]) j = next[j];
    if(c[i] == c[j+1]) next[i] = j+1;
    else next[i] = 0;
  }
  LL ans = 0;
  Go(i , 2 , n) {
    int j = i;
    while(next[j]) j = next[j];
    if(next[i]) next[i] = j;
    ans += 1ll * (i - j);
  }

  std::cout << ans << "\n";
  return 0;
}