题目大意：给你n个字符串，求∑∑f^2(si,sj)，其中f(s,t)的定义是s的前缀跟t的后缀的最长匹配长度。

∑|si|<=1e6，n<=1e5

官方题解：字符串hash出来所有的字符串的后缀，然后枚举所有字符串的前缀看匹不匹配并记录到cnt数组里，但是这时候cnt中会有重复，比如样例，在枚举aba的前缀a,ab,aba时a被多计算了cnt[3]次，因为在匹配上aba时，对a的匹配是无效的，因为求得是最长匹配所以cnt[1]-=cnt[3]，至于aba为什么对应a就很显然是next数组可以求出来了,next[3]=1（当然如果是abc的话就不存在多算，因为前缀是a,ab,abc；后缀是c,bc,abc，只有到abc才匹配上，a跟c没关系，next[3]=0）即最后要cnt[next[i]]-=cnt[i]

AC代码：

#if(__cplusplus == 201103L)
#include <unordered_map>
#include <unordered_set>
#else
#include <tr1/unordered_map>
#include <tr1/unordered_set>
namespace std
{using std::tr1::unordered_map;using std::tr1::unordered_set;
}
#endif
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
const int maxn=1e5+10;
const LL mod=998244353;
string s[maxn];
char b[maxn*10];
LL cnt[maxn*10];
int n;
int nxt[maxn*10];
ULL base=131;
unordered_map<ULL,LL> mp;
void get_next(int len)
{nxt[1]=0;for(int i=2,j=0;i<=len;i++){while(j>0&&b[i]!=b[j+1]) j=nxt[j];if(b[i]==b[j+1]) j++;nxt[i]=j;}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cin>>n;ULL S,opt;int len;for(int i=1;i<=n;i++){cin>>s[i];S=0;len=(int)s[i].size();opt=1;for(int j=len-1;j>=0;j--){S=S+opt*s[i][j];opt*=base;mp[S]++;}}LL ans=0;for(int i=1;i<=n;i++){len=(int)s[i].size();for(int j=0;j<len;j++) b[j+1]=s[i][j];get_next(len);S=0;for(int j=1;j<=len;j++){S=S*base+b[j];if(mp[S]) cnt[j]=mp[S];else cnt[j]=0;cnt[nxt[j]]-=cnt[j];}for(LL j=1;j<=len;j++){ans=(((j*j)%mod)*cnt[j]+ans)%mod;}}cout<<ans<<endl;
}
/*
样例：
3
ab
ba
aba输出：
29
*/