题解 E 我不爱她

我用的是一个 hash+KMP 的做法。

首先，先把所有后缀的 hash 值记录下来，存入 map 中。

然后查询每一个前缀，求出 hash 值相同的后缀数量乘上长度的和即为答案。

但有些情况会算重复，比如 ababa 中 a 的答案在 aba 处被多算了,aba 的答案在 ababa 的地方被多算了。

其实，多算的位置就是自己的与自己匹配，就是 KMP 的 next 数组。

求出 next 即可。

hash 时注意多加一些值，比如长度。

#include<bits/stdc++.h>
#define re //register
#define int long long
using namespace std;
int t,n,nxt[1500002],pw[1500002];
string s[100002];
unordered_map<int,int>v;
#define M 1000000007ll
signed main(){
    std::ios::sync_with_stdio(false);
       for(re int i=pw[0]=1;i<=1500000;++i)pw[i]=131ll*pw[i-1]%M;
    cin>>t;
    while(t--){
        cin>>n;v.clear();
        for(re int i=1;i<=n;++i)cin>>s[i];
        for(re int i=1;i<=n;++i){
            re int x=s[i].length()-1,hsh=0;
            for(re int j=x;~j;--j){
                hsh=(131ll*hsh%M+s[i][j]-'a'+1)%M;
                ++v[hsh+(x-j+1)*M];
            }
        }
        long long ans=0;
        for(re int j=1;j<=n;++j){
            re int x=s[j].length(),k=0,hsh=0;
            for(re int i=x;i;--i)s[j][i]=s[j][i-1];
            for(re int i=2;i<=x;++i){
                while(k&&(s[j][i]^s[j][k+1]))k=nxt[k];
                nxt[i]=s[j][i]==s[j][k+1]?++k:k;
            }
            for(re int i=1;i<=x;++i){hsh=(hsh+1ll*(s[j][i]-'a'+1)*pw[i-1]%M)%M;ans+=v[hsh+i*M]*(i-nxt[i]);}
        }
        cout<<ans<<endl;
    }

}