F - Birthday Cake(山东省赛)

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

我的想法就是看一个字符串的前缀和后缀,如果这两个前后缀相等，就去查询这个字符串除去这个前后缀之后还剩下的部分是否出现过，然后统计出现次数的答案 ps 我们把所有串按照串的长度从小到大排个序，一定要排，不然aaaa,aa这个数据就可以卡掉。

//我还是不清楚为什么我第一遍写的代码错了
//看官方题解我觉得思路很对呀,,,呜呜呜呜呜
//官方是双哈希做的,<<昨晚因为本题特意acwing学的哈希表>>
//出题人卡了自然溢出和一些常见模数的单哈希，所以要用双哈希，ps:如果是确定是哈希题，看到通过率很离谱的时候，可以考虑双哈希的可能。
//blog.csdn.net/weixin_45672411/article/details/116720502
//如果不会哈希,建议去看acwing841,再回来看这题就很简单了;
#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;//或者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();
}
//区间和公式 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()
{
    
    //求大于1e9的最小质数,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; //秦九韶算法,131进制转10进制
        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++)
        {
      //前缀和公式 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;
}