当前位置:网站首页>F - Birthday Cake(山东省赛)
F - Birthday Cake(山东省赛)
2022-07-06 09:25:00 【是小张张呀 zsy】
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;
}
边栏推荐
- Crawler series (9): item+pipeline data storage
- Learning records: serial communication and solutions to errors encountered
- C语言必背代码大全
- Learning record: Tim - Basic timer
- ucore lab 2
- Indonesian medical sensor Industry Research Report - market status analysis and development prospect forecast
- 51 lines of code, self-made TX to MySQL software!
- ucorelab3
- JS --- BOM details of JS (V)
- Market trend report, technological innovation and market forecast of pneumonia drugs obtained by Chinese hospitals
猜你喜欢
随机推荐
Es6---es6 content details
How to change XML attribute - how to change XML attribute
Intensive learning notes: Sutton book Chapter III exercise explanation (ex17~ex29)
csapp shell lab
Mysql database (IV) transactions and functions
ucore lab 6
学习记录:使用STM32外部输入中断
China medical check valve market trend report, technical dynamic innovation and market forecast
Learning record: how to perform PWM output
Mysql database (I)
Cost accounting [14]
What if software testing is too busy to study?
ucore lab7
LeetCode#412. Fizz Buzz
How to do agile testing in automated testing?
Leetcode notes - dynamic planning -day7
STM32学习记录:LED灯闪烁(寄存器版)
Learning record: use STM32 external input interrupt
Cost accounting [21]
[C language] twenty two steps to understand the function stack frame (pressing the stack, passing parameters, returning, bouncing the stack)