2019上海网络赛G-Substring_字符串Hash+自建Hashmap_算法日常[26/100]

题目链接

计蒜客走你(揍你)

题意

  • 定义匹配 : 两个串首尾字母相同,中间整个串相同或者是相同数量的各字符组成的不同排列
  • 给你一个原串S,然后给你m个子串t,求这些子串在原串S中匹配的个数
  • 无关题意的个人吐槽:众所周知,2019最后一场网络赛-上海网络赛是一场让你自闭的计数场

题解

  • 长度种类数是O($\sqrt n$)的
  • 然后就是离线暴力处理—>hash字符串
  • 对hash字符串比较匹配
  • 但是如果使用unordered_map会超时
  • 使用数组会超内存
  • 只有使用自建hash才能过
  • 详见代码注释
  • 代码是借鉴一个大佬同学的

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define pre(i,a,n) for(int i=n;i>=a;--i)
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#ifdef ONLINE_JUDGE
const int N = 1e5+50;
#else
const int N = 1e2+10;
#endif

char s[N],p[N];
int n, m;
const int bas = 1e9+7;
ull get(int *a) {
ull ret = 0;
rep(i,0,27) {
ret = ret*bas+a[i]+1;
}
return ret;
}
struct node {
ull sta;
int id;
};
vector<node> g[N];


int ans[N];
ull fac[N];

int clk;

// 手写的Hash,因为unorder_map<int,int> f[26][26]被卡时间
namespace Hash{
const int hashmod = 218357;
int v[hashmod];
unsigned long long h[hashmod];
int vis[hashmod];
int &get(unsigned long long S) {
int t2 = S % hashmod, i;
// vis[i]是访问过的(clk恒为1),所以也要走下一个
// h[i] = S.则发生了hash crash(哈希碰撞),就要走到下一个,也就是h[i] != S 走下一个
// i = t2-1说明走了一个轮回了,就不用再走了,再走就是重复走t2位置了,所以i!=t2-1
for (i = t2; vis[i]==clk && h[i] != S && i != t2 - 1; i = (i + 1) % hashmod);
// 从未访问过的要初始化计数值为0
if (vis[i]!=clk) h[i] = S, vis[i] = clk, v[i] = 0;
return v[i];
}
};

void solve() {
scanf("%s",s+1);
n = strlen(s+1);
rep(i,1,n) g[i].clear();
scanf("%d",&m);
rep(i,1,m) {
scanf("%s",p+1);
int len = strlen(p+1);
node ret;
ret.id = i;
int cnt[28]{};
rep(i,1,len) ++cnt[p[i]-'a'];
cnt[26] = p[1];
cnt[27] = p[len];
ret.sta = get(cnt);
g[len].pb(ret);
}
rep(i,1,m) ans[i] = 0;
rep(len,1,n) if (g[len].size()) {
int cnt[28]{};
// 中间的字母是按照字母顺序来的,所以就是可以的,然后最后两个是按照直接首尾字母来的
rep(i,1,len) ++cnt[s[i]-'a'];
cnt[26] = s[1];
cnt[27] = s[len];
ull sta = get(cnt);
++clk;
for (int L=1,R=len; R<=n; ++L,++R) {
++Hash::get(sta);
// 左边字符基底为一个fac,而右边为fac^0=1
sta = sta+(s[L+1]-s[L])*fac[1];
sta = sta+(ll)(s[R+1]-s[R]);
// 下面是右移一位整体的字母表的hash值变化
sta = sta-fac[27-(s[L]-'a')];
sta = sta+fac[27-(s[R+1]-'a')];
}
// 这个t长度下,把各次提问的ans更新
// hash是这个头尾相同,中间的串是不同排列的 询问串(key) ————> 原串中的个数(value)
for (auto &&t:g[len]) ans[t.id] = Hash::get(t.sta);
}
rep(i,1,m) printf("%d\n",ans[i]);
}

int main() {
fac[0]=1;
rep(i,1,30) fac[i]=fac[i-1]*bas;
int t;
scanf("%d",&t);
while (t--) solve();
}

每天一句叨叨

所有的胜利,与征服自己的胜利比起来,都是微不足道。所有的失败,与失去自己的失败比起来,更是微不足道

点击查看

本文标题:2019上海网络赛G-Substring_字符串Hash+自建Hashmap_算法日常[26/100]

文章作者:单林敏

发布时间:2019年09月16日 - 21:33:16

最后更新:2019年10月17日 - 19:20:28

原始链接:https://www.wolfdan.cn/算法日常-26-100/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

-------------------本文结束 感谢您的阅读-------------------
0%