前几天打牛客的多校，今天写这个题发现是基本一样的题，改成多组输入，map改成unordered_map（不然会t），最后的乘平方改成乘一次就好了，不要取模。

先对所有的字符串后缀hash，用unordered_map记录每个hash值（后缀）有多少个一样的。这个地方后缀的 hash 值可以将字符串倒过来求，每次乘以base^ i ，这和字符串正着求每次 t=t *base + s 是一样的，可以想象一下，前后缀相同位置乘base的次数是一样的。然后遍历所有的前缀的hash，在unordered_map里找当前 hash 值出现的次数的记录下来，最后把符合条件的长度平方乘以个数加起来，即ans+=mp[hash]* i 。但是这样会有多算的部分，比如 f("aba","aba")，当遍历到 i=1 的时候，会加上一次，遍历到 i=3 的时候也会加上一次。这时应该选择 i=3的时候加上，把 i=1的时候舍去，这样就要用到kmp算法了，可以看出next[3]=1，只要在 i=3 的时候减去 next[3] 就好了。

代码： 
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define ft first
#define sd second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;

int nt[1501000];
int base=233;
unordered_map<ull,int> mp;
string s[1501000];
int res[1501000];

void kmp_nt(string p)
{
    nt[0]=0;
    for(int i=1,j=0;i<p.size();i++){
        while(p[i]!=p[j]&&j) j=nt[j-1];
        if(p[i]==p[j]) j++;
        nt[i]=j;
    }
}

void Hash(string s)
{
    ull t=0,p=1;
    for(int i=s.size()-1;i>=0;i--){
        t+=p*(s[i]-'a'+1);
        p*=base;
        mp[t]++;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        memset(nt, 0, sizeof(nt));
        memset(res, 0, sizeof(res));
        mp.clear();
        ll ans=0;
        for(int i=0;i<n;i++) cin>>s[i],Hash(s[i]);
        for(int i=0;i<n;i++){
            ull t=0;
            for(int j=0;j<s[i].size();j++){
                t=t*base+s[i][j]-'a'+1;
                res[j]=mp[t];
            }
            kmp_nt(s[i]);
            for(int j=0;j<s[i].size();j++){
                if(nt[j]) res[nt[j]-1]-=res[j];
            }
            for(int j=0;j<s[i].size();j++){
                ans+=res[j]*(j+1);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}