import java.io.*;
import java.util.*;
class selling_rna {
static int mod = (int) (1e9 + 7);
static PrintWriter out = new PrintWriter(System.out);
public static class Trie {
private class Node {
Node A;
Node U;
Node G;
Node C;
boolean isend = false;
HashSet<Integer> set = new HashSet<>();
public String toString() {
StringBuilder sb = new StringBuilder();
if (A != null) {
sb.append("A | ");
}
if (U != null) {
sb.append("U | ");
}
if (G != null) {
sb.append("G | ");
}
if (C != null) {
sb.append("C | ");
}
sb.append(set);
sb.append("\n");
return sb.toString();
}
}
/** Initialize your data structure here. */
Node root;
public Trie() {
root = new Node();
}
public String toString() {
Node curr = root;
StringBuilder sb = new StringBuilder();
Queue<Node> qu = new ArrayDeque<>();
qu.add(curr);
while (qu.size() != 0) {
Node rem = qu.remove();
sb.append(rem);
if (rem.A != null) {
qu.add(rem.A);
}
if (rem.U != null) {
qu.add(rem.U);
}
if (rem.G != null) {
qu.add(rem.G);
}
if (rem.C != null) {
qu.add(rem.C);
}
}
return sb.toString();
}
/** Inserts a word into the trie. */
public void insert(String word, int idx) {
Node curr = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
curr.set.add(idx);
if (ch == 'A') {
if (curr.A == null) {
curr.A = new Node();
}
curr = curr.A;
} else if (ch == 'U') {
if (curr.U == null) {
curr.U = new Node();
}
curr = curr.U;
} else if (ch == 'G') {
if (curr.G == null) {
curr.G = new Node();
}
curr = curr.G;
} else if (ch == 'C') {
if (curr.C == null) {
curr.C = new Node();
}
curr = curr.C;
}
}
curr.set.add(idx);
curr.isend = true;
}
public HashSet<Integer> query(String s) {
Node curr = root;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == 'A') {
if (curr.A == null) {
return new HashSet<>();
}
curr = curr.A;
} else if (ch == 'U') {
if (curr.U == null) {
return new HashSet<>();
}
curr = curr.U;
} else if (ch == 'G') {
if (curr.G == null) {
return new HashSet<>();
}
curr = curr.G;
} else if (ch == 'C') {
if (curr.C == null) {
return new HashSet<>();
}
curr = curr.C;
}
}
return curr.set;
}
/**
* Returns if there is any word in the trie that starts with the given prefix.
*/
}
static void solve() {
int n = i();
int m = i();
Trie t1 = new Trie();
Trie t2 = new Trie();
for (int i = 0; i < n; i++) {
String s = s();
t1.insert(s, i);
String rev = reverses(s);
t2.insert(rev, i);
}
for (int i = 0; i < m; i++) {
String L = s();
String R = s();
R=reverses(R);
HashSet<Integer> set1 = t1.query(L);
HashSet<Integer> set2 = t2.query(R);
// System.err.println(set1 + " " + set2);
int ans=0;
for(int val:set1){
if(set2.contains(val)){
ans++;
}
}
System.out.println(ans);
}
// System.err.println(t2);
// System.err.println(t1);
}
private static String reverses(String s) {
StringBuilder sb = new StringBuilder();
sb.append(s);
sb.reverse();
return sb.toString();
}
public static void main(String[] args) {
int test = 1;
while (test-- > 0) {
solve();
}
out.flush();
out.close();
}
// ------> swap(long[]arr,int idx1,int idx2)<---- swap int
// ----->segmentTree--> segTree as class
// ----->lazy_Seg_tree --> lazy_Seg_tree as class
// -----> Trie --->Trie as class
// ----->fenwick_Tree ---> fenwick_Tree
// -----> POWER ---> long power(long x, long y) <----
// -----> LCM ---> long lcm(long x, long y) <----
// -----> GCD ---> long gcd(long x, long y) <----
// -----> SIEVE --> ArrayList<Integer> sieve(int N) <-----
// -----> NCR ---> long ncr(int n, int r) <----
// -----> BINARY_SEARCH ---> int binary_Search(long[]arr,long x) <----
// -----> (SORTING OF LONG, CHAR,INT) -->long[] sortLong(long[] a2)<--
// ----> DFS ---> void dfs(ArrayList<ArrayList<Integer>>edges,int child,int
// parent)<---
// ---> NODETOROOT --> ArrayList<Integer>
// node2Root(ArrayList<ArrayList<Integer>>edges,int child,int parent,int tofind)
// <--
// ---> LEVELS_TREE -->levels_Trees(ArrayList<HashSet<Integer>> edges, int
// child, int parent,int[]level,int currLevel) <--
// ---> K_THPARENT --> int k_thparent(int node,int[][]parent,int k) <---
// ---> TWOPOWERITHPARENTFILL --> void twoPowerIthParentFill(int[][]parent) <---
// -----> (INPUT OF INT,LONG ,STRING) -> int i() long l() String s()<-
// tempstart
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int Int() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public String String() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public String next() {
return String();
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
static InputReader in = new InputReader(System.in);
public static int i() {
return in.Int();
}
public static long l() {
String s = in.String();
return Long.parseLong(s);
}
public static String s() {
return in.String();
}
public static int compareChar(char a, char b) {
return Character.compare(a, b);
}
public static int compareInt(int a, int b) {
return Integer.compare(a, b);
}
public static int compareLong(long a, long b) {
return Long.compare(a, b);
}
public static boolean compareString(String a, String b) {
return a.equals(b);
}
public static boolean compareStringBuilder(StringBuilder a, StringBuilder b) {
return a.equals(b);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
8292 KB |
Output is correct |
| 2 |
Correct |
92 ms |
8252 KB |
Output is correct |
| 3 |
Correct |
97 ms |
8180 KB |
Output is correct |
| 4 |
Correct |
88 ms |
8336 KB |
Output is correct |
| 5 |
Correct |
86 ms |
8192 KB |
Output is correct |
| 6 |
Correct |
85 ms |
8344 KB |
Output is correct |
| 7 |
Correct |
77 ms |
8132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1579 ms |
222432 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1557 ms |
44288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
8292 KB |
Output is correct |
| 2 |
Correct |
92 ms |
8252 KB |
Output is correct |
| 3 |
Correct |
97 ms |
8180 KB |
Output is correct |
| 4 |
Correct |
88 ms |
8336 KB |
Output is correct |
| 5 |
Correct |
86 ms |
8192 KB |
Output is correct |
| 6 |
Correct |
85 ms |
8344 KB |
Output is correct |
| 7 |
Correct |
77 ms |
8132 KB |
Output is correct |
| 8 |
Execution timed out |
1579 ms |
222432 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
