F - birthday cake (Shandong race)

Moca’s birthday is coming up, and her friend Ran is going to the Yamabuki bakery to order a birthday cake for her.

Yamabuki bakery provides nn kinds of cake. Since Ran knows that Moca is the Yamabuki Bakery’s 11-st fan and can eat a lot of food, she intends to order two cakes and put them together into a big cake. The cake made by Yamabuki bakery can be formed by a string consisting of lowercase Latin letters, which describes the toppings on the cake, such as strawberries and chocolate. Putting two cakes together is the concatenation of two corresponding strings. For example, the result of putting cake ab and cake cabc together is a big cake abcabc.

To make it easier to share the cake, Ran will choose two cakes and put them together into a big cake which can be divided in half into two identical pieces. For example, cake abcabc will be divided in half into two cakes abc, but cake abbc will be divided in half into two different cakes ab and bc. Notice that Ran can not reverse the cake, which means that cake abba will be divided into two different cakes ab and ba.

Can you help Ran figure out how many different pairs of cakes meet the above condition?

Input
The first line contains one integer n(1≤n≤4e5)– the number of cakes.

The next n lines describe all the cakes, where the ii-th line contains one string si(1≤∣s ≤4e5)consisting of lowercase Latin letters.

It is guaranteed that the sum of lengths of cakes does not exceed 4e5

Output
Print one integer – the number of pairs of cakes meet the above condition.
Inputcopy
3
ab
ab
cabc
Outputcopy
3

My idea is to look at the prefix and suffix of a string , If these two prefixes are equal , Just check whether the remaining part of the string after removing the pre suffix has ever appeared , Then count the number of answers ps We arrange all strings according to their length from small to large , Be sure to row , Otherwise aaaa,aa This data can be stuck out .

// I still don't know why I wrote the wrong code for the first time 
// Looking at the official explanation, I think the idea is very right ,,, Purr, purr, purr 
// The official is double hash ,<< Last night because of this topic acwing Learned hash table >>
// The questioner got stuck with natural overflow and some common modulus single hashes , So use double hash ,ps: If yes, it is a hash problem , When you see that the pass rate is outrageous , Consider the possibility of double hashing .
//blog.csdn.net/weixin_45672411/article/details/116720502
// If you can't hash , Suggest to see it acwing841, Coming back to this question, it's very simple ;
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>PII;
map<PII,int>ma;
int const N=4e5+10;
int P=131;// perhaps p=13331;
ll p1[N],p2[N],h1[N],h2[N];
ll const mod1=1e9+7,mod2=1e9+9;
int n;
char s[N];
string ss[N];

bool cmp(string s1,string s2)
{
    
    return s1.size()<s2.size();
}
// Interval and formula  h[l,r]=h[r]−h[l−1]×P[r−l+1];
ll check1(int l,int r)
{
    
    if(l>r)
        return 0;
    return (h1[r]-h1[l-1]*p1[r-l+1]%mod1+mod1)%mod1;
}

ll check2(int l,int r)
{
    
    if(l>r)
        return 0;
    return (h2[r]-h2[l-1]*p2[r-l+1]%mod2+mod2)%mod2;
}

int main()
{
    
    // Find greater than 1e9 The smallest prime number ,1e9+7,1e9+9;
    /* int flag=2; for(ll i=1000000000; ;i++) { int kk=0; for(ll j=2;j<=i/j;j++) { if(i%j==0) { kk=1; break; } } if(kk==0) { cout<<i<<endl; flag--; } if(!flag) break; }*/
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    p1[0]=1,p2[0]=1;
    for(int i=1; i<N; i++)
    {
    
        p1[i]=p1[i-1]*P%mod1; // Horner scheme ,131 Turn into the system 10 Base number 
        p2[i]=p2[i-1]*P%mod2;
    }
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>ss[i];
    sort(ss+1,ss+1+n,cmp);
    ll ans=0;
    for(int i=1; i<=n; i++)
    {
    
        int len=ss[i].size();
        for(int j=1; j<=len; j++)
            s[j]=ss[i][j-1];
        for(int j=1; j<=len; j++)
        {
      // Prefixes and formulas  h[i+1]=h[i]*P+s[i];
            h1[j]=(h1[j-1]*P%mod1+s[j])%mod1;
            h2[j]=(h2[j-1]*P%mod2+s[j])%mod2;
        }
        for(int j=1;j<=len-j+1;j++)
        {
    
            int r=len-j+1;
            if(check1(1,j)==check1(r,len)&&check2(1,j)==check2(r,len))
            {
    
                ans+=ma[{
    check1(j+1,r-1),check2(j+1,r-1)}];
            }
        }
        ans+=ma[{
    check1(1,len),check2(1,len)}];
        ma[{
    check1(1,len),check2(1,len)}]++; 
    }
    cout<<ans<<endl;
    return 0;
}