wolfdan's blog

0%

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

发表于 更新于 分类于 Valine：
思维题 手写HashMap StringHash 串按长度分类讨论 2019上海网络赛G-Substring_字符串Hash+自建Hashmap 所有的胜利，与征服自己的胜利比起来，都是微不足道。所有的失败，与失去自己的失败比起来，更是微不足道

题目链接

计蒜客走你(揍你)

题意

  • 定义匹配 : 两个串首尾字母相同,中间整个串相同或者是相同数量的各字符组成的不同排列
  • 给你一个原串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();
}

每天一句叨叨

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

相关文章