哈希 WA on 24 求调
  • 板块CF113B Petr#
  • 楼主zhanglh
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/28 14:11
  • 上次更新2024/12/28 17:11:41
查看原帖
哈希 WA on 24 求调
726862
zhanglh楼主2024/12/28 14:11
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const int N = 200010;
const ll MOD = 1e9 + 7;
const ll P = 998244353;

const int base = 13331;

string s, st, ed;
int n, ls, le, file[2010];
ull h[2010], p[2010];

ull get(int l, int r) {
    if (l == 0) return h[r];
    return h[r] - h[l - 1] * p[r - l + 1];
}

void solve() { //Hash
    cin >> s >> st >> ed;
    n = s.size();
    ls = st.size();
    le = ed.size();
    ull hash_st = 0;
    for (int i = 0; i < ls; i++) {
        hash_st *= base;
        hash_st += st[i];
    }
    ull hash_ed = 0;
    for (int i = 0; i < le; i++) {
        hash_ed *= base;
        hash_ed += ed[i];
    }
    h[0] = s[0];
    p[0] = 1;
    for (int i = 1; i < s.size(); i++) {
        h[i] = h[i - 1] * base + s[i];
        p[i] = p[i - 1] * base;
    }
    set<ull> S;
    for (int i = 0; i < n; i++) {
        for (int j = i; j + le - 1 < n; j++) {
            if (get(i, i + ls - 1) == hash_st && get(j, j + le - 1) == hash_ed) {
                //cout << i << " " << j + le - 1 << "\n";
                S.insert(get(i, j + le - 1));
            }
        }
    }
    printf("%lld\n", S.size());
}

int main() {
    int tcs;
    //scanf("%d", &tcs);
    tcs = 1;
    while(tcs--) {
        solve();
    }
    return 0;
}
2024/12/28 14:11
加载中...