#include <bits/stdc++.h>
using namespace std;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define v vector
#define mp make_pair
typedef long long ll;
typedef pair<int, int > pii;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
void io() {
#ifdef LOCAL_PROJECT
freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else
#endif
ios_base::sync_with_stdio(false); cin.tie(NULL);
}
/*************************JOI16_selling_rna***************************************/
int N, M;
int conv(char c) {
if (c == 'A') return 0;
if (c == 'C') return 1;
if (c == 'U') return 2;
return 3;
}
struct Node {
int nxt[4];
v<int> str;
Node() { memset(nxt, -1, sizeof nxt); }
v<int> getChildren() {
v<int> chi;
FOR(i, 0, 4) if (nxt[i] != -1) chi.push_back(nxt[i]);
return chi;
}
};
struct Trie {
Node t[4'000'009];
int tsz = 1;
int dfstim = 0;
int P[100001]; // for -(1-N)
int L[100001], R[100001]; // for +(1-M)
void addTrieNode(string &s, int num) {
int cur = 0;
for (char &cc : s) {
int c = conv(cc);
if (t[cur].nxt[c] == -1)
t[cur].nxt[c] = tsz++;
cur = t[cur].nxt[c];
}
t[cur].str.push_back(num);
}
void dfs(int cur) {
if (t[cur].str.size()>0)
dfstim++;
for (int x : t[cur].str)
if (x < 0) P[abs(x)] = dfstim;
else L[x] = dfstim;
v<int> adj = t[cur].getChildren();
for (auto nex : adj)
dfs(nex);
if (t[cur].str.size()>0)
dfstim++;
for (int x : t[cur].str)
if (x > 0) R[x] = dfstim;
}
} tfor, trev;
int main() {
io();
cin >> N >> M;
FORE(i, 1, N) {
string s; cin >> s;
tfor.addTrieNode(s, -i);
reverse(all(s));
trev.addTrieNode(s, -i);
}
FORE(i, 1, M) {
string p, q; cin >> p >> q;
tfor.addTrieNode(p, i);
reverse(all(q));
trev.addTrieNode(q, i);
}
tfor.dfs(0);
trev.dfs(0);
//FORE(i, 1, N) {
// printf("org str; point @ (%d, %d) \n", tfor.P[i], trev.P[i]);
//}
//FORE(i, 1, M) {
// printf("org query; rect @ x(%d, %d), y(%d, %d) \n", tfor.L[i], tfor.R[i], trev.L[i], trev.R[i]);
//}
FORE(i, 1, M) {
int ans = 0;
FORE(k, 1, N) if (tfor.L[i] <= tfor.P[k] && tfor.P[k] <= tfor.R[i] && trev.L[i] <= trev.P[k] && trev.P[k] <= trev.R[i])
ans++;
cout << ans << "\n";
}
}
Compilation message
selling_rna.cpp:42:10: warning: multi-character character constant [-Wmultichar]
Node t[4'000'009];
^~~~~
selling_rna.cpp:42:15: error: invalid digit "9" in octal constant
Node t[4'000'009];
^~~
selling_rna.cpp:42:10: error: expected ']' before '\x303030'
Node t[4'000'009];
^~~~~
selling_rna.cpp: In member function 'void Trie::addTrieNode(std::__cxx11::string&, int)':
selling_rna.cpp:53:8: error: 't' was not declared in this scope
if (t[cur].nxt[c] == -1)
^
selling_rna.cpp:55:10: error: 't' was not declared in this scope
cur = t[cur].nxt[c];
^
selling_rna.cpp:57:3: error: 't' was not declared in this scope
t[cur].str.push_back(num);
^
selling_rna.cpp: In member function 'void Trie::dfs(int)':
selling_rna.cpp:61:7: error: 't' was not declared in this scope
if (t[cur].str.size()>0)
^
selling_rna.cpp:63:16: error: 't' was not declared in this scope
for (int x : t[cur].str)
^
selling_rna.cpp:67:16: error: 't' was not declared in this scope
v<int> adj = t[cur].getChildren();
^
