51nod 1304 字符串的相似度 exkmp

题意

我们定义2个字符串的相似度等于两个串的相同前缀的长度。例如 “abc” 同 “abd” 的相似度为2，”aaa” 同 “aaab” 的相似度为3。
给出一个字符串S，计算S同他所有后缀的相似度之和。例如：S = “ababaa”，所有后缀为：

ababaa 6
babaa 0
abaa 3
baa 0
aa 1
a 1

S同所有后缀的相似度的和 = 6 + 0 + 3 + 0 + 1 + 1 = 11

输入一个字符串S(1 <= L <= 1000000)，L为字符串S的长度，且S由a-z的小写字母组成。

分析

就是一个简单的exkmp，把extend数组累加上就好了
如果你一定要后缀自动机跳LCA，或者后缀数组RMQ处理我也没有办法

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll N = 1000010;

char ss[N]; ll extend[N];

int main()
{
  scanf("%s",ss+1); ll len = strlen(ss+1); extend[1] = len;
  for(ll i=1;i<=len;i++) if(ss[i] != ss[i+1]){extend[2] = i-1; break;}ll p=2; ll mx = p+extend[2]-1;
  ll ans=0; for(ll i=3;i<=len;i++)
  {
    if(i<mx) extend[i] = min(extend[i-p+1] , mx-i+1);
    while(ss[i+extend[i]] == ss[extend[i]+1]) extend[i]++;
    if(i+extend[i]-1 > mx){mx = i+extend[i]-1; p=i;}
    ans+=extend[i];
  }

  return printf("%lld\n",ans+extend[2]+extend[1]),0;
}