A.All with Pairs（Hash+Kmp） 2020牛客暑期多校训练营（第二场）

本文主要是介绍A.All with Pairs（Hash+Kmp） 2020牛客暑期多校训练营（第二场），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目都很短就懒得写题意了。

思路：
把每个字符的后缀都用hash表示然后用map存起来算数目。
统计的时候，对于当前的前缀我们可以算出其在后缀中出现的次数。
但问题是这样可能有重复。
解决办法是：$cnt[next[i]]-=cnt[i]$
因为假设p1是p2的最长公共前后缀，那么p2对于出现的后缀，被p1对应出现的后缀包含，且不能用，所以减掉。

至于为什么只需要找最长公共前后缀，而不需要找到所有将p1作为后缀的串，是因为如果p1是p2的后缀，但不是最长的后缀，那么p2对应的后缀一定包含在next[p2]对应的后缀中。

kmp的计算方式和这题很像。
Count the string HDU3336（KMP+DP，统计前缀数目）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6 + 7;
const int base = 233;
const int mod = 998244353;
char s[maxn];
int n;
vector<ull>Hash[maxn];
vector<int>Next[maxn];
ull P[maxn];
int cnt[maxn];
unordered_map<ull,int>mp;
ll ans;void init() {P[0] = 1;for(int i = 1;i < maxn;i++) {P[i] = P[i - 1] * base;}
}void getNext(int x) {int len = strlen(s + 1);Next[x].resize(len + 1);for(int i = 2;i <= len;i++) {int j = Next[x][i - 1];while(j && s[i] != s[j + 1]) {j = Next[x][j];}Next[x][i] = s[i] == s[j + 1] ? j + 1 : 0;}
}void getHash(int x) {int len = strlen(s + 1);Hash[x].resize(len + 1);for(int i = 1;i <= len;i++) {Hash[x][i] = Hash[x][i - 1] * base + s[i];}for(int i = 0;i < len;i++) {ull h = Hash[x][len] - Hash[x][i] * P[len - i];mp[h]++;}
}void get(int x) {getNext(x);getHash(x);
}int main() {init();int n;scanf("%d",&n);for(int i = 1;i <= n;i++) {scanf("%s",s + 1);get(i);}for(int i = 1;i <= n;i++) {int len = Hash[i].size() - 1;for(int j = 1;j <= len;j++) {cnt[j] = mp[Hash[i][j]];cnt[Next[i][j]] -= cnt[j];}for(int j = 1;j <= len;j++) {ans = (1ll * cnt[j] * j % mod * j % mod + ans) % mod;}}printf("%lld\n",ans);return 0;
}

这篇关于A.All with Pairs（Hash+Kmp） 2020牛客暑期多校训练营（第二场）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---