【2021牛客寒假第四场】B题 武辰延的字符串 二分+哈希

传送门：https://ac.nowcoder.com/acm/contest/9984/B

题意

给字符串s和t，问有多少种s的两个前缀相连是t的前缀的个数。

思路

首先这题暴力n^2肯定会T的。 正确解法是先找s的前缀s1和t的前半部分配对，再找s的最长前缀s2和t的后半部分配对，贡献为s2的长度。

如何配对? 区间字符串哈希!

关于字符串哈希，就是将一个区间的字符段用一个整数表示，在没有哈希冲突的情况下，这个整数就代表独一无二的字符段。

如何找最长前缀？ 二分！

Code

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
##include "bits/stdc++.h"

using namespace std;
typedef unsigned long long ull;

const ull mod = 131;
const int N = 1e5 + 10;
ull p[N];
ull sums[N], sumt[N];
char s[N], t[N];
int lens, lent;

ull hashs(int l, int r) {
    return sums[r] - sums[l - 1] * p[r - l + 1];
}

ull hasht(int l, int r) {
    if(r > lent) return 0;
    return sumt[r] - sumt[l - 1] * p[r - l + 1];
}

void solve() {
    cin >> (s + 1) >> (t + 1);
    lens = strlen(s + 1), lent = strlen(t + 1);
    p[0] = 1;
    for(int i = 1;i <= max(lens, lent); i++) {
        if(i <= lens) sums[i] = sums[i - 1] * mod + s[i];
        if(i <= lent) sumt[i] = sumt[i - 1] * mod + t[i];
        p[i] = p[i - 1] * mod;
    }

    ull ans = 0;
    for(int i = 1;i <= lent - 1; i++) {
        if(s[i] != t[i]) break; // 先匹配第一个s1
        if(t[i + 1] != s[1]) continue;
        int l = 1, r = lens, res = 0;
        while(l <= r) { // 二分找出最长前缀
            int mid = (l + r) / 2;
            if(hashs(1, mid) == hasht(i + 1, i + mid)) {
                res = mid; l = mid + 1;
            }
            else r = mid - 1;
        }
        ans += res;
    }
    cout << ans << endl;
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/02/19/2021-nowcoder-hanjia-4-b/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！