牛客国庆集训派对Day5 H题我不爱她

本文主要是介绍牛客国庆集训派对Day5 H题我不爱她，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

（有任何问题欢迎留言或私聊 && 欢迎交流讨论哦

Catalog

文章目录

- - Catalog
  - - Problem：传送门
  - Solution：
  - - AC_Code：
    - Problem Description：

Problem：传送门

Portal

原题目描述在最下面。

Solution：

先放一个群里某大佬的解释：

就是一个串w是a的前缀也是b的后缀
那么border(w)也是a的前缀也是b的后缀
(因为border(w)是w的前缀也是w的后缀)
所以把每个w的贡献记为len(w) - len(border(w))
如果w被匹配了说明border(w)一定不是最长的相当于加上len(w)的时候把不是最长的len(border(w))贡献去掉
最后累加起来剩下的都是最长的

在告诉你一个小秘密：

int ans = 0, t = 0;
for(int i = len; i > 0; ) {ans += i - nex[i];i = nex[i];p[t++] = nex[i];
}
printf("ans = %d\n", ans);///ans 的值和这个字符串的长度一样哦！！！
///只有p数组里存的前缀才是这个字符串的后缀！(如果这句话是错的，望大佬指出！

讲讲我的理解吧

如那位大佬所言，若字符串 $w$ 是所求的巧合值，也就是 $w$ 是 $a$ 的后缀，也是 $b$ 的后缀，同样 $b o r d e r (w)$ 也满足此条件，只不过 $l e n (b o r d e r (w)) < l e n (w)$ 。

问题在于，你对每两个字符串求 $b o r d e r$ 时间上肯定 $t l e$ 了。怎么解决呢？

题解上讲的是每个前缀/后缀的贡献记为 $l e n (w) - l e n (b o r d e r (w))$ 。

然后你把所有的前缀子串贡献记为 $l e n (i) - l e n (b o r d e r (i))$ ，再用 $m a p$ 存一下每个前缀 $o r$ 后缀的出现次数。最后遍历一遍所有后缀或前缀，累加贡献即可。

我上面写了只有 $p$ 数组里的前缀才会是这个字符串的后缀！而且每个字符串不会有算重复的地方， $p$ 数组求一遍 $k m p$ 的 $f a i l$ 数组就行了。

AC_Code：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <unordered_map>
#define fi first
#define se second
#define iis std::ios::sync_with_stdio(false)
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<LL, LL> pii;
/*
就是一个串w是a的前缀也是b的后缀
那么border(w)也是a的前缀也是b的后缀
(因为border(w)是w的前缀也是w的后缀)
所以把每个w的贡献记为len(w) - len(border(w))
如果w被匹配了 说明border(w)一定不是最长的 相当于加上len(w)的时候 把不是最长的len(border(w))贡献去掉
最后累加起来剩下的都是最长的
int ans = 0, t = 0;
for(int i = len; i > 0; ) {ans += i - nex[i];i = nex[i];p[t++] = nex[i];
}
printf("ans = %d\n", ans);///ans 的值和这个字符串的长度一样哦！！！
///只有p数组里存的前缀才是这个字符串的后缀！(如果这句话是错的，望大佬指出！
*/
const long long HMOD[] = {2078526727, 2117566807};
const long long BASE[] = {1572872831, 1971536491};
const int MXN = 1e5 + 5;
const int MXT = 1e6 + 5e5 + 6;char s[MXT];
int fail[MXT];
std::vector<pii> ve;
unordered_map<LL, int> mp;
void get_fail(char *t,int m) {fail[0] = -1;for(int i = 0,k = -1; i < m;) {if(k == -1 || t[i] == t[k]) {++ i; ++ k;fail[i] = k;}else k = fail[k];}
}
int main(int argc, char const *argv[]) {LL N = (int)2e9, hh;int tim;scanf("%d", &tim);while(tim--) {ve.clear();mp.clear();int n; scanf("%d", &n);for(int i = 0; i < n; ++i) {scanf("%s", s);int len = strlen(s);get_fail(s, len);pii tmp = {0, 0};for(int i = 0; i < len; ++i) {tmp.fi = (tmp.fi*BASE[0] + (s[i]-'a'+1))%HMOD[0];tmp.se = (tmp.se*BASE[1] + (s[i]-'a'+1))%HMOD[1];hh = tmp.fi*N + tmp.se;ve.push_back({hh, i + 1 - fail[i + 1]});}tmp = {0, 0};LL p1 = 1, p2 = 1;for(int i = len - 1; i >= 0; --i) {tmp.fi = (tmp.fi + (s[i]-'a'+1)*p1)%HMOD[0];tmp.se = (tmp.se + (s[i]-'a'+1)*p2)%HMOD[1];hh = tmp.fi*N + tmp.se;mp[hh] ++;p1 = p1 * BASE[0] % HMOD[0];p2 = p2 * BASE[1] % HMOD[1];}}int len = ve.size();LL ans = 0;for(int i = 0; i < len; ++i) {ans += mp[ve[i].first]*ve[i].se;}printf("%lld\n", ans);}return 0;
}
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <unordered_map>
#define fi first
#define se second
#define iis std::ios::sync_with_stdio(false)
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<LL, LL> pii;const int MXN = 1e5 + 5;
const int MXT = 1e6 + 5e5 + 6;
const LL mod = 999999999999989ll;
const LL base = 99957;
int n;
vector<int> g[MXN];
char s[MXT];
int ch[MXT][2], CNT;
int fail[MXT];
LL hs[MXT];
unordered_map<LL, LL> mp;
int newnode() {++ CNT;ch[CNT][0] = ch[CNT][1] = -1;return CNT;
}
void Insert(vector<int> vs, int len) {fail[0] = -1;int rt = 0;for(int i = 0, k = -1; i < len; ) {if(k == -1 || vs[i] == vs[k]) {++ i; ++ k;fail[i] = k;if(ch[rt][vs[i-1]] == -1) {ch[rt][vs[i-1]] = newnode();}hs[ch[rt][vs[i-1]]] = (hs[rt] * base + vs[i-1] + 'a') % mod;rt = ch[rt][vs[i-1]];mp[hs[rt]] += i - fail[i];printf("%d %lld\n", i - fail[i], hs[rt]);}else k = fail[k];}
}
int main(){int T;scanf("%d",&T);while(T--){mp.clear();CNT = 0;ch[0][0] = ch[0][1] = -1;scanf("%d", &n);for(int j = 0, len; j < n; ++j) {scanf("%s", s);len = strlen(s);for(int i = 0; i < len; ++i) {g[j].push_back(s[i]-'a');}Insert(g[j], len);}LL ans=0;for(int i = 0, len; i < n; ++i) {len = g[i].size();LL p1 = 1, tmp = 0;for(int j = len - 1; j >= 0; --j) {tmp = (tmp + (g[i][j] + 'a') * p1) % mod;p1 = p1 * base % mod;ans += mp[tmp];}g[i].clear();}printf("%lld\n",ans);}
}

Problem Description：

终于活成了自己讨厌的样子。

天空仍灿烂，它爱着大海。

你喜欢大海，我爱过你。

世界上充满了巧合。我们把每句话当成一个字符串，我们定义a对b的巧合值为a的最长后缀的长度并且它是恰好是b的前缀，这里的后缀或者前缀包括字符串的本身。
比如字符串“天空仍灿烂她喜欢大海”对“她喜欢大海我不爱她了我爱的只是与她初见时蔚蓝的天空”的巧合值为5，而字符串“她喜欢大海我不爱她了我爱的只是与她初见时蔚蓝的天空”对“天空仍灿烂她喜欢大海”的巧合值为2。
现在给出n个字符串由"ab"构成的字符串s1,s2,…,sn，求出对于所有1≤ i,j≤ n，si对sj的巧合值的和。