QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#845311 | #1942. Another Substring Query Problem | CYYH | RE | 0ms | 0kb | C++20 | 2.6kb | 2025-01-06 15:52:15 | 2025-01-06 15:52:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define il inline
#define ptc putchar
#define pb push_back
#define R(i, l, r) for (int i = l; i <= r; ++i)
#define debug puts("--------------------------------------------")
typedef long long ll;
typedef pair<int, int> PII;
namespace ZT {
template <typename T>
il void read(T &x) {
x = 0; T f = 1; char ch;
while (!isdigit(ch = getchar())) f -= (ch == '-') << 1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch & 15), ch = getchar();
x *= f;
}
template <typename T, typename ...L>
il void read(T &x, L &...y) {read(x); read(y...);}
template <typename T>
il void write(T x) {
if (x < 0) ptc('-'), x = -x;
if (x > 9) write(x / 10);
ptc(x % 10 + '0');
}
template <typename T, typename ...L>
il void write(T &x, L &...y) {write(x), ptc(' '); write(y...);}
}
using namespace ZT;
#define int ll
const int N = 2e5 + 5, P = 1e9 + 7;
char s[N];
int n, q, k, B;
ll hsh[N], base[N] = {1};
char t[N];
void init() {
R(i, 1, n) {
base[i] = base[i - 1] * 131 % P;
hsh[i] = (hsh[i - 1] * 131 % P + s[i] - 'a') % P;
}
}
ll get(int l, int r) {
return (hsh[r] - hsh[l - 1] * base[r - l + 1] % P + P) % P;
}
unordered_map <int, int> vis[201];
vector <int> str[201][N];
// unordered_map <ll, vector <int> > str;
signed main() {
scanf("%s", s + 1); n = strlen(s + 1); B = 200;
init(); int tot = 0;
// cout << get(1, 3) << ' ' << get(2, 4) << endl;
R(j, 1, B) {
R(i, 1, n) {
if (i + j - 1 > n) break;
ll v = get(i, i + j - 1);
if (!vis[j][v]) vis[j][v] = ++tot;
str[j][vis[j][v]].push_back(i);
}
}
read(q);
while (q--) {
scanf("%s", t + 1); read(k); int m = strlen(t + 1);
ll now = 0;
R(i, 1, m) now = (now * 131 + t[i] - 'a') % P;
int id = vis[m][now];
if (m <= B) {
if (!vis[m][now]) {
puts("-1");
continue;
}
// cout << str[id][0] << ' ' << str[id][1] << '\n';
if (str[m][id].size() < k) puts("-1");
else write(str[m][id][k - 1]), ptc('\n');
} else {
R(i, 1, n - m + 1) {
ll v = get(i, i + m - 1);
if (v == now) --k;
if (!k) {
write(i), ptc('\n');
break;
}
}
if (k) puts("-1");
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh...