#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 1e5 + 10, alphabet = 26;
int n, m;
string rna[maxn];
struct query
{
string p, q;
}ask[maxn];
void input()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
cin >> rna[i];
for (int i = 1; i <= m; i ++)
cin >> ask[i].p >> ask[i].q;
}
struct sub_trie
{
unordered_map < int, sub_trie * > child;
int cnt;
sub_trie()
{
//for (int i = 0; i < alphabet; i ++)
// child[i] = NULL;
cnt = 0;
}
int add(string &word, int pos)
{
cnt ++;
if (pos == word.size())
return 0;
int go = word[pos] - 'A', to_add = 0;
if (child[go] == NULL)
{
to_add = 0;
child[go] = new sub_trie();
}
return to_add + child[go] -> add(word, pos + 1);
}
int find_suffix(string &word, int pos)
{
if (pos == word.size())
return cnt;
int go = word[pos] - 'A';
if (child[go] == NULL)
return 0;
return child[go] -> find_suffix(word, pos + 1);
}
};
void merge_sub_trie(sub_trie *&prim, sub_trie *sec)
{
if (sec == NULL)
return;
if (prim == NULL)
{
prim = sec;
return;
}
prim -> cnt += sec -> cnt;
for (int i = 0; i < alphabet; i ++)
{
if (sec -> child[i] != NULL)
merge_sub_trie(prim -> child[i], sec -> child[i]);
}
}
struct trie
{
unordered_map < int, trie * > child;
sub_trie *suffix;
int suffix_len;
vector < pair < string, int > > tasks;
trie()
{
suffix_len = 0;
suffix = new sub_trie();
}
void add(string &word, int pos)
{
if (pos == word.size())
{
string temp = word;
reverse(temp.begin(), temp.end());
suffix_len += suffix -> add(temp, 0);
return;
}
int go = word[pos] - 'A';
if (child[go] == NULL)
child[go] = new trie();
child[go] -> add(word, pos + 1);
}
void push_query(string &word, int pos, string &suff, int idx)
{
if (pos == word.size())
{
tasks.push_back({suff, idx});
return;
}
int go = word[pos] - 'A';
if (child[go] == NULL)
return;
child[go] -> push_query(word, pos + 1, suff, idx);
}
};
trie *root = new trie();
void build_trie()
{
for (int i = 1; i <= n; i ++)
{
root -> add(rna[i], 0);
}
}
void insert_queries()
{
for (int i = 1; i <= m; i ++)
{
reverse(ask[i].q.begin(), ask[i].q.end());
root -> push_query(ask[i].p, 0, ask[i].q, i);
}
}
int ans[maxn];
void dfs(trie *root)
{
int mx = -1, max_len = -1;
for (int i = 0; i < alphabet; i ++)
{
if (root -> child[i] != NULL)
{
dfs(root -> child[i]);
if (root -> child[i] -> suffix_len > max_len)
{
max_len = root -> child[i] -> suffix_len;
mx = i;
}
}
}
if (mx != - 1)
{
swap(root -> suffix, root -> child[mx] -> suffix);
}
for (int i = 0; i < alphabet; i ++)
{
if (root -> child[i] == NULL)
continue;
merge_sub_trie(root -> suffix, root -> child[i] -> suffix);
}
for (pair < string, int > cur : root -> tasks)
{
ans[cur.second] = root -> suffix -> find_suffix(cur.first, 0);
}
}
void solve_queries()
{
dfs(root);
for (int i = 1; i <= m; i ++)
cout << ans[i] << endl;
}
void solve()
{
input();
build_trie();
insert_queries();
solve_queries();
}
int main()
{
speed();
solve();
return 0;
}
/**
*/
Compilation message
selling_rna.cpp: In member function 'int sub_trie::add(std::string&, int)':
selling_rna.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | if (pos == word.size())
| ~~~~^~~~~~~~~~~~~~
selling_rna.cpp: In member function 'int sub_trie::find_suffix(std::string&, int)':
selling_rna.cpp:63:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | if (pos == word.size())
| ~~~~^~~~~~~~~~~~~~
selling_rna.cpp: In member function 'void trie::add(std::string&, int)':
selling_rna.cpp:108:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | if (pos == word.size())
| ~~~~^~~~~~~~~~~~~~
selling_rna.cpp: In member function 'void trie::push_query(std::string&, int, std::string&, int)':
selling_rna.cpp:125:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | if (pos == word.size())
| ~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
10196 KB |
Output is correct |
| 2 |
Correct |
6 ms |
10104 KB |
Output is correct |
| 3 |
Correct |
6 ms |
10196 KB |
Output is correct |
| 4 |
Correct |
6 ms |
10100 KB |
Output is correct |
| 5 |
Correct |
5 ms |
10188 KB |
Output is correct |
| 6 |
Correct |
6 ms |
10016 KB |
Output is correct |
| 7 |
Correct |
7 ms |
10100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
645 ms |
473364 KB |
Output is correct |
| 2 |
Correct |
650 ms |
467208 KB |
Output is correct |
| 3 |
Runtime error |
1137 ms |
1048576 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
12428 KB |
Output is correct |
| 2 |
Correct |
30 ms |
17168 KB |
Output is correct |
| 3 |
Correct |
31 ms |
15768 KB |
Output is correct |
| 4 |
Correct |
24 ms |
11596 KB |
Output is correct |
| 5 |
Correct |
49 ms |
28288 KB |
Output is correct |
| 6 |
Correct |
38 ms |
21308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
10196 KB |
Output is correct |
| 2 |
Correct |
6 ms |
10104 KB |
Output is correct |
| 3 |
Correct |
6 ms |
10196 KB |
Output is correct |
| 4 |
Correct |
6 ms |
10100 KB |
Output is correct |
| 5 |
Correct |
5 ms |
10188 KB |
Output is correct |
| 6 |
Correct |
6 ms |
10016 KB |
Output is correct |
| 7 |
Correct |
7 ms |
10100 KB |
Output is correct |
| 8 |
Correct |
645 ms |
473364 KB |
Output is correct |
| 9 |
Correct |
650 ms |
467208 KB |
Output is correct |
| 10 |
Runtime error |
1137 ms |
1048576 KB |
Execution killed with signal 9 |
| 11 |
Halted |
0 ms |
0 KB |
- |
