QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#837074 | #9568. Left Shifting 3 | laonongmin | Compile Error | / | / | C++20 | 2.0kb | 2024-12-29 14:56:08 | 2024-12-29 14:56:08 |
Judging History
This is the latest submission verdict.
- [2024-12-29 14:56:08]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2024-12-29 14:56:08]
- Submitted
answer
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 计算字符串哈希值的函数(简单的多项式哈希示例)
const int p = 31;
const int m = 1e9 + 9;
vector<long long> p_pow;
// 预处理p的幂
void precompute_pow(int n) {
p_pow.resize(n);
p_pow[0] = 1;
for (int i = 1; i < n; i++) {
p_pow[i] = (p_pow[i - 1] * p) % m;
}
}
// 计算字符串的哈希值
vector<long long> compute_hash(const string& s) {
int n = s.length();
vector<long long> h(n + 1);
h[0] = 0;
for (int i = 0; i < n; i++) {
h[i + 1] = (h[i] + (s[i] - 'a' + 1) * p_pow[i]) % m;
}
return h;
}
// 获取子串的哈希值
long long get_hash(const vector<long long>& h, const int& l, const int& r, const vector<long long>& p_pow) {
long long res = h[r + 1] - h[l];
res = (res + m) % m;
res = (res * p_pow[n - r - 1]) % m;
return res;
}
int main() {
int T;
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;
string s;
cin >> s;
precompute_pow(n);
// 计算“nanjing”的哈希值
string target = "nanjing";
vector<long long> target_hash = compute_hash(target);
int target_val = target_hash.back();
int max_count = 0;
for (int d = 0; d <= k; d++) {
string shifted_s = s.substr(d) + s.substr(0, d);
vector<long long> shifted_hash = compute_hash(shifted_s);
int count = 0;
int len = shifted_s.length();
for (int l = 0; l < len; l++) {
for (int r = l; r < len; r++) {
long long sub_hash = get_hash(shifted_hash, l, r, p_pow);
if (sub_hash == target_val) {
count++;
}
}
}
if (count > max_count) {
max_count = count;
}
}
cout << max_count << endl;
}
return 0;
}
Details
answer.code: In function ‘long long int get_hash(const std::vector<long long int>&, const int&, const int&, const std::vector<long long int>&)’: answer.code:35:24: error: ‘n’ was not declared in this scope 35 | res = (res * p_pow[n - r - 1]) % m; | ^