山东省省赛F题题解
链接：https://ac.nowcoder.com/acm/contest/15600/F
来源：牛客网
题目描述
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 nnn kinds of cake. Since Ran knows that Moca is the Yamabuki Bakery's 111-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 ababab and cake cabccabccabc together is a big cake abcabcabcabcabcabc.
To make it easier to hare 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 abcabcabcabcabcabc will be divided in half into two cakes abcabcabc, but cake abbcabbcabbc will be divided in half into two different cakes ababab and bcbcbc. Notice that Ran can not reverse the cake, which means that cake abbaabbaabba will be divided into two different cakes ababab and bababa.
Can you help Ran figure out how many different pairs of cakes meet the above condition?
输入描述:
The first line contains one integer nnn (1≤n≤4⋅105)(1 \le n \le 4 \cdot 10^5)(1≤n≤4⋅105) -- the number of cakes.
The next nnn lines describe all the cakes, where the iii-th line contains one string sis_isi (1≤∣si∣≤4⋅105)(1 \le |s_i| \le 4 \cdot 10^5)(1≤∣si∣≤4⋅105) consisting of lowercase Latin letters.
It is guaranteed that the sum of lengths of cakes does not exceed 4⋅1054 \cdot 10^54⋅105.
输出描述:
Print one integer -- the number of pairs of cakes meet the above condition.
示例1
输入
3
ab
ab
cabc输出
3示例2
输入
3
abc
a
cabc输出
0示例3
输入
4
hhh
hhh
hhh
hhh输出
6官网题解
image-20210623160849075官方题解的思路，考虑每举一个串i的时候，我们去枚举这个串长度相同的前后缀，然后如果这两个前后缀相等，就去查询串i 出去这个前后缀之后还剩下的部分是否出现过，然后统计出现次数的答案即可，前后缀相等既可以用哈希判断也可以先做一遍k m p 求出n e x t 来统计答案，正确性画画图挺清晰的。
另：需要排序，防止a，aa这种情况出现。需要双哈希才能过。
参考链接
2021山东省大学生程序设计竞赛 F - Birthday Cake （思维 + 双哈希）
代码
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
map<pair<ll, ll>, ll> mp;
ll Next[400500] = {0};
string str[400500];
void get_next(string t)
{
Next[0] = -1;
ll j = 0, k = -1;
while (j < t.size())
{
if (k == -1 || t[j] == t[k])
Next[++j] = ++k;
else
k = Next[k];
}
}
const ll base1 = 13331;
const ll base2 = 13331;
const ll MOD1 = 1e9 + 7;
const ll MOD2 = 1e9 + 9;
ll hs1[4000500] = {0}, hs2[400500] = {0}, be1[400500] = {0}, be2[400500] = {0};
ll get1(ll l, ll r)
{
return ((hs1[r] - hs1[l - 1] * be1[r - l + 1]) % MOD1 + MOD1) % MOD1;
}
ll get2(ll l, ll r)
{
return ((hs2[r] - hs2[l - 1] * be2[r - l + 1]) % MOD2 + MOD2) % MOD2;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll n;
cin >> n;
be1[0] = be2[0] = 1;
for (ll i = 1; i <= 400000; i++)
{
be1[i] = be1[i - 1] * base1 % MOD1;
be2[i] = be2[i - 1] * base2 % MOD2;
}
for (ll i = 1; i <= n; i++)
cin >> str[i];
sort(str + 1, str + 1 + n, [](string a, string b)
{ return a.size() < b.size(); });
ll ans = 0;
for (ll i = 1; i <= n; i++)
{
get_next(str[i]);
int val = Next[str[i].size()];
for (ll j = 1; j <= str[i].size(); j++)
hs1[j] = (hs1[j - 1] * base1 + str[i][j - 1] - 'a' + 1) % MOD1;
for (ll j = 1; j <= str[i].size(); j++)
hs2[j] = (hs2[j - 1] * base2 + str[i][j - 1] - 'a' + 1) % MOD2;
while (val != -1)
{
if (val + 1 <= str[i].size() - val)
{
ll aim1 = get1(val + 1, str[i].size() - val), aim2 = get2(val + 1, str[i].size() - val);
ans += mp[{aim1, aim2}];
}
val = Next[val];
}
mp[{get1(1, str[i].size()), get2(1, str[i].size())}]++;
}
cout << ans << endl;
}