BirthdayCake

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 $n$ kinds of cake. Since Ran knows that Moca is the Yamabuki Bakery's $1$ -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?

The first line contains one integer $n$ $(1 \le n \le 4 \cdot 10^5)$ -- the number of cakes.

The next $n$ lines describe all the cakes, where the $i$ -th line contains one string $s_i$ $(1 \le |s_i| \le 4 \cdot 10^5)$ consisting of lowercase Latin letters.

It is guaranteed that the sum of lengths of cakes does not exceed $4 \cdot 10^5$ .

#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> #define int long long #define LL __int128 using namespace std; const int N=4e5+10; const int base=131,mod=1e18+3; LL h[N],pw[N]; int n,id[N],res; string str[N]; unordered_map<int,int> mp; LL get(int l,int r){return (h[r]-h[l-1]*pw[r-l+1]%mod+mod)%mod;} signed main(){ cin>>n; pw[0]=1; for(int i=1;i<=n;i++) cin>>str[i],id[i]=i; for(int i=1;i<N;i++) pw[i]=pw[i-1]*base%mod; sort(id+1,id+1+n,[](int a,int b){return str[a].size()<str[b].size();}); for(int i=1,m;i<=n;i++){ h[0]=str[id[i]][0],m=str[id[i]].size()-1; for(int j=1;j<=m;j++) h[j]=(h[j-1]*base+str[id[i]][j])%mod; for(int j=(m+1)/2;j<m;j++) if(get(0,m-j-1)==get(j+1,m)) res+=mp[get(m-j,j)]; res+=mp[h[m]]++; } cout<<res; return 0; }

详情