/**
* Author : Nguyen Tuan Vu
* Created : 02.12.2022
**/
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
template <class X, class Y> bool minimize(X &a, Y b) {
if (a > b) return a = b, true;
return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
if (a < b) return a = b, true;
return false;
}
using namespace std;
mt19937 jdg(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {return l + jdg() % (r - l + 1);}
void file(){
#define TASK "TASK"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
}
const int N = 1e5 + 5;
int n, nquery;
string s[N];
namespace sub4 {
struct TRIE_PREF {
struct node {
node *child[26];
int L, R;
node() {
L = -1, R = -1;
REP(i, 26) child[i] = NULL;
}
} *root;
TRIE_PREF() {
root = new node();
}
void add(string &x, int ID) {
node *p = root;
for (auto c : x) {
if (p -> child[c - 'A'] == NULL) p -> child[c - 'A'] = new node();
p = p -> child[c - 'A'];
if (p -> L == -1) p -> L = p -> R = ID;
else p -> R = ID;
}
}
pair <int, int> get(string &x) {
node *p = root;
for (auto c : x) {
if (p -> child[c - 'A'] == NULL) return make_pair(-1, 0);
p = p -> child[c - 'A'];
}
return make_pair(p -> L, p -> R);
}
} pref;
struct TRIE_SUFF {
struct node {
node *child[26];
vector <int> S;
int dd;
node() {
dd = 0;
REP(i, 26) child[i] = NULL;
}
} *root;
TRIE_SUFF() {
root = new node();
}
void add(string &x, int ID) {
node *p = root;
for (auto c : x) {
if (p -> child[c - 'A'] == NULL) p -> child[c - 'A'] = new node();
p = p -> child[c - 'A'];
p -> S.push_back(ID);
}
}
int get(string &x, int L, int R) {
node *p = root;
for (auto c : x) {
if (p -> child[c - 'A'] == NULL) return 0;
p = p -> child[c - 'A'];
}
return upper_bound(ALL(p -> S), R) - lower_bound(ALL(p -> S), L);
}
void process() {
if (root -> dd == 1) return;
root -> dd = 1;
sort (ALL(root -> S));
REP(i, 26) if (root -> child[i] != NULL) {
node *p = root;
root = root -> child[i];
process();
root = p;
}
}
} suff;
const int base = 31;
const int Mod = 1e9 + 7;
vector <int> Hash[N];
int Pow[N], ID[N];
int getHash(int i, int l, int r) {
return (Hash[i][r] - 1ll * Hash[i][l - 1] * Pow[r - l + 1] % Mod + Mod) % Mod;
}
void solve() {
FOR(i, 1, n) {
Hash[i].resize(s[i].size() + 7, 0);
REP(j, s[i].size()) Hash[i][j + 1] = (1ll * Hash[i][j] * base % Mod + s[i][j] - 'A' + 1) % Mod;
}
Pow[0] = 1;
FOR(i, 1, 1e5) Pow[i] = 1ll * Pow[i - 1] * base % Mod;
FOR(i, 1, n) ID[i] = i;
sort (ID + 1, ID + n + 1, [] (int &x, int &y) {
int l = -1, r = min((int) s[x].size(), (int) s[y].size()) + 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (getHash(x, 1, mid) == getHash(y, 1, mid)) l = mid;
else r = mid;
}
if (l == min((int) s[x].size(), (int) s[y].size())) {
return (s[x].size() <= s[y].size());
}
return (s[x][l] <= s[y][l]);
});
FOR(i, 1, n) {
pref.add(s[ID[i]], i);
reverse(ALL(s[ID[i]]));
suff.add(s[ID[i]], i);
}
suff.process();
while (nquery--) {
string PREF, SUFF;
cin >> PREF >> SUFF;
reverse(ALL(SUFF));
pair <int, int> Pref = pref.get(PREF);
int Suff = suff.get(SUFF, Pref.first, Pref.second);
cout << Suff << '\n';
}
}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
file();
cin >> n >> nquery;
FOR(i, 1, n) cin >> s[i];
sub4::solve();
cerr << "Time elapsed: " << TIME << " s.\n";
return 0;
}
/*
==================================================+
INPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
Compilation message
selling_rna.cpp: In function 'void file()':
selling_rna.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | freopen(TASK".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | freopen(TASK".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6228 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6228 KB |
Output is correct |
| 3 |
Correct |
5 ms |
6228 KB |
Output is correct |
| 4 |
Correct |
4 ms |
6228 KB |
Output is correct |
| 5 |
Correct |
4 ms |
6228 KB |
Output is correct |
| 6 |
Correct |
4 ms |
6172 KB |
Output is correct |
| 7 |
Correct |
4 ms |
6228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
540 ms |
571184 KB |
Output is correct |
| 2 |
Runtime error |
54 ms |
32844 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
17492 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6228 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6228 KB |
Output is correct |
| 3 |
Correct |
5 ms |
6228 KB |
Output is correct |
| 4 |
Correct |
4 ms |
6228 KB |
Output is correct |
| 5 |
Correct |
4 ms |
6228 KB |
Output is correct |
| 6 |
Correct |
4 ms |
6172 KB |
Output is correct |
| 7 |
Correct |
4 ms |
6228 KB |
Output is correct |
| 8 |
Correct |
540 ms |
571184 KB |
Output is correct |
| 9 |
Runtime error |
54 ms |
32844 KB |
Execution killed with signal 11 |
| 10 |
Halted |
0 ms |
0 KB |
- |
