纯粹一个模板题。
不过我发现我广义后缀自动机竟然没写笔记,太奇怪了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<string>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=1001000;
const int root=1;
struct Sam
{
int last,cnt;
int n,k;
int nt[maxn<<1][26],fa[maxn<<1];
int len[maxn<<1],sum[maxn<<1];
int x[maxn<<1],y[maxn<<1];
int ha[maxn<<1],f[maxn<<1];
char str[maxn];
void init(void)
{
last=root;
cnt=1;
fa[1]=0;
len[1]=0;
}
void _insert(int c)
{
if(nt[last][c])
{
int p=last,q=nt[p][c];
if(len[q]==len[p]+1) last=q;
else
{
int nowq=++cnt;
len[nowq]=len[p]+1;
memcpy(nt[nowq],nt[q],sizeof(nt[q]));
fa[nowq]=fa[q];
fa[q]=nowq;
while(p&&nt[p][c]==q) nt[p][c]=nowq,p=fa[p];
last=nowq;
}
}
else
{
int nowp=++cnt,p=last;
len[nowp]=len[last]+1;
while(p&&!nt[p][c]) nt[p][c]=nowp,p=fa[p];
if(!p) fa[nowp]=root;
else
{
int q=nt[p][c];
if(len[q]==len[p]+1) fa[nowp]=q;
else
{
int nowq=++cnt;
len[nowq]=len[p]+1;
memcpy(nt[nowq],nt[q],sizeof(nt[q]));
fa[nowq]=fa[q];
fa[nowp]=fa[q]=nowq;
while(p&&nt[p][c]==q) nt[p][c]=nowq,p=fa[p];
}
}
last=nowp;
}
return ;
}
void creat(void)
{
init();
for(int i=1;i<=n;i++)
{
scanf("%s",str);
last=root;
int len=strlen(str);
for(int j=0;j<len;j++)
_insert(str[j]-'a');
}
return ;
}
ll get_ans(void)
{
ll ans=0;
for(int i=1;i<=cnt;i++)
ans=ans+len[i]-len[fa[i]];
return ans;
}
void print_ans(void)
{
printf("%lld\n",get_ans());
return ;
}
}sam;
int main(void)
{
scanf("%d%d",&sam.n,&sam.k);
sam.creat();
sam.print_ans();
return 0;
}