首页 > 代码库 > Cutting （暴力 + 滚动哈希判字符串匹配）

Cutting （暴力 + 滚动哈希判字符串匹配）

2024-09-15 21:08:12   220人阅读

技术分享

题意：

给你两串小写字符串a和b，问能否将a拆成三段重新组成b

做法：

枚举拆分位置，也就是C(2,4999)。然后judge时用滚动哈希判断字符串是否匹配。

PS：

WA了好多发，因为爆int（忘记1LL，取模没取好...）。滚动哈希不一定能A，但基本都能A。

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;
const int mod = 1e9 + 7;
int hahb = 0;
int f[5050];
int hah[5050];
string a, b;
int len;
bool judge(int i, int j) {
    int hah1 = hah[i-1];
    int hah2 = (hah[j-1] - 1LL * hah[i-1] * f[j-i] % mod + mod) % mod;
    int hah3 = (hah[len-1] - 1LL * hah[j-1] * f[len - j] % mod + mod) % mod;
    // abc
    if( ((1LL * hah1 * f[len-i] % mod + 1LL * hah2 * f[len-j] % mod) % mod + hah3) % mod == hahb ) return true;
    // acb
    if( ((1LL * hah1 * f[len-i] % mod + 1LL * hah3 * f[j-i] % mod) % mod + hah2) % mod == hahb ) return true;
    // bac
    if( ((1LL * hah2 * f[i+len-j] % mod + 1LL * hah1 * f[len-j] % mod) % mod + hah3) % mod == hahb ) return true;
    // bca
    if( ((1LL * hah2 * f[i+len-j] % mod + 1LL * hah3 * f[i] % mod) % mod + hah1) % mod == hahb ) return true;
    // cab
    if( ((1LL * hah3 * f[j] % mod + 1LL * hah1 * f[j-i] % mod) % mod + hah2) % mod == hahb ) return true;
    // cba
    if( ((1LL * hah3 * f[j] % mod + 1LL * hah2 * f[i] % mod) % mod + hah1) % mod == hahb ) return true;
    return false;
}
int main() {
    f[0] = 1;
    for(int i = 1; i < 5010; i++) f[i] = (1LL * f[i-1] * 26) % mod; //记录进位
    cin >> a >> b;
    len = a.size();
    for(int i = 0; i < len; i++) hahb = (1LL * hahb * 26 + b[i] - ‘0‘) % mod; //计算b的哈希值
    hah[0] = a[0] - ‘0‘;
    for(int i = 1; i < len; i++) {
        hah[i] = (1LL * hah[i-1] * 26 + a[i] - ‘0‘) % mod;  //计算a[0]到a[i]字串的哈希值
    }
    for(int i = 1; i < len; i++) {
        for(int j = i+1; j < len; j++) {
            if( judge(i, j) ) {
                puts("YES");
                for(int k = 0; k < len; k++) {
                    if(k == i || k == j) putchar(‘\n‘);
                    printf("%c", a[k]);
                }
                putchar(‘\n‘);
                return 0;
            }
        }
    }
    puts("NO");
}

Cutting （暴力 + 滚动哈希判字符串匹配）


联系
我们