2020牛客暑期多校训练营（第二场） All with Pairs (kmp、hash_map)

链接：https://ac.nowcoder.com/acm/contest/5667/A
来源：牛客网

All with Pairs

时间限制：C/C++ 3秒，其他语言6秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

示例1

输入

3
ab
ba
aba

输出

29

说明

解法：所有前缀和后缀的数目为O(∑|si|) ，可以先将所有后缀的hash值统计（此处使用hash_map）

定义cnt[i] 数组表示对长度为i的相同前后缀对答案的贡献，

现在开始处理cnt[i] 数组的值：

对于每一个给定的字符串s[i] ，进行一遍getnext()处理，得到nt[i]数组，

枚举每个字符串长度为 j 的前缀，用hash_map获取与该前缀相同的后缀数目 x ，cnt[ j ]+=x，还要cnt[ nt[ j ] ] -= x ;

现在解释为什么要cnt[ nt[ j ] ] -= x：

由于题目求的是两字符串前后缀最长匹配，则当出现更长的匹配串时，较短匹配串的贡献就无效了需要减去，而nt[j]存的就是该前缀中的次短匹配长度(kmp算法)，所以需要将次短匹配长度的贡献减去 x ; 

例如：“aba” 和 “aba” 匹配时 ，存在两种前后缀匹配情况：“a”、“aba” 

当j=1时 “a”，cnt[1]+=x；

当j=3时 “aba”，出现更长匹配情况，则cnt[j]+=x，还需减去之前“a”对答案的贡献 cnt[ nt[3] ]-=x;

#include<bits/stdc++.h>
#define ll long long
#define pai pair<ll,ll>
using namespace std;
int n;
string s[100005];
ll mod[2]={1000000007,998244353};
ll base[2]={43,47};
ll f[2][1000006];
ll h[2][1000006];const ll mood=1e9+7;
const int maxsz=3e6+7;//hash_map模板 
template<typename key,typename val>
class hash_map{public:struct node{key u;val v;int next;};vector<node> e;int head[maxsz],nume,numk,id[maxsz];int geths(pair<ll,ll> &u){int x=(1ll*u.first*mood+u.second)%maxsz;if(x<0) return x+maxsz;return x;}val& operator[](key u){int hs=geths(u);for(int i=head[hs];i;i=e[i].next)if(e[i].u==u) return e[i].v;if(!head[hs])id[++numk]=hs;if(++nume>=e.size())e.resize(nume<<1);return e[nume]=(node){u,0,head[hs]},head[hs]=nume,e[nume].v;}void clear(){for(int i=0;i<=numk;i++) head[id[i]]=0;numk=nume=0;}
};
hash_map<pair<ll,ll>,ll> mp;void init()
{f[0][0]=f[1][0]=1ll;for(int i=1;i<1000006;i++){f[0][i]=f[0][i-1]*base[0]%mod[0];f[1][i]=f[1][i-1]*base[1]%mod[1];}	
}ll gethash(int l,int r,int id)//获取哈希值 
{return (h[id][r]-h[id][l-1]*f[id][r-l+1]%mod[id]+mod[id])%mod[id];
}int nt[1000006];
ll cnt[1000006];
ll modd =998244353;
void getnext(string s)
{int i=0,k=-1;int len=s.size();nt[0]=-1;while(i<len){if(k==-1||s[i]==s[k]){i++;k++;nt[i]=k;//nt处理范围 [0,len] }else k=nt[k];}
}
int main()
{init();cin>>n;for(int i=1;i<=n;i++)	{cin>>s[i];}for(int i=1;i<=n;i++){int len=s[i].size();ll now0=0,now1=0; for(int j=0;j<len;j++)//双哈希 {int tmp=s[i][j]-'a'+1;now0=(now0*base[0]%mod[0]+tmp)%mod[0];h[0][j+1]=now0;now1=(now1*base[1]%mod[1]+tmp)%mod[1];h[1][j+1]=now1;}pai pp;for(int j=0;j<len;j++){pp.first=gethash(j+1,len,0);pp.second=gethash(j+1,len,1);mp[pp]++;//记录后缀数目 }}for(int i=1;i<=n;i++){int len=s[i].size();ll now0=0,now1=0; for(int j=0;j<len;j++)//双哈希 {int tmp=s[i][j]-'a'+1;now0=(now0*base[0]%mod[0]+tmp+mod[0])%mod[0];h[0][j+1]=now0;now1=(now1*base[1]%mod[1]+tmp+mod[1])%mod[1];h[1][j+1]=now1;}getnext(s[i]);//kmp_next处理 for(int j=1;j<=len;j++){pai p;p.first=gethash(1,j,0);p.second=gethash(1,j,1);ll x=mp[p];cnt[j]+=x;cnt[nt[j]]=(cnt[nt[j]]-x+modd)%modd;//去重  抹去上个较短后缀贡献 }}ll ans=0;for(int i=1;i<1000006;i++){ans=(ans+(1ll*cnt[i]*i*i%modd)+modd)%modd;}printf("%lld\n",ans);}