51nod 1304 字符串的相似度

题意

我们定义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

前言

很明显地就是让你求扩展KMP的f指针，全部加起来就是答案了
以前的时候，看到这题，只会SAM，然后卡空间，觉得大毒瘤
今天讲课的时候提了一下扩展KMP
然后发现很简单QAQ
教程就不写了。。
自己随便用笔画一画估计都能画出来。。

CODE:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=1000005;
char ss[N];
int len;
int f[N];
void get_f()
{f[1]=len;int st=0,ed=0;for (int u=2;u<=len;u++){if (ed>=u)  f[u]=min(ed-u+1,f[u-st+1]);while (u+f[u]<=len&&ss[u+f[u]]==ss[f[u]+1]) f[u]++;if (u+f[u]>=ed) {ed=u+f[u]-1;st=u;}}
}
int main()  
{scanf("%s",ss+1);len=strlen(ss+1);get_f();long long ans=0;for (int u=1;u<=len;u++)    ans=ans+f[u];printf("%I64d\n",ans);return 0;
}