Subtask 1

~N, M, |S_i|, |P_j|, |Q_j|~ có giá trị nhỏ. Chúng ta có thể giải quyết nhiệm vụ con này bằng cách kiểm tra tất cả các chuỗi RNA cho mỗi yêu cầu.

Subtask 2

Ta có thể tiếp cận bài toán này bằng thuật toán Hash. Cụ thể, các bước thực hiện như sau:

Bước 1: Khởi tạo mảng Hash Đầu tiên, ta sẽ khởi tạo mảng Hash cho tất cả các xâu ~S_i~ với ~1 \leq i \leq N~.

Bước 2: Xử lý truy vấn Với mỗi truy vấn gồm hai xâu ~P~ và ~Q~, ta thực hiện các bước sau:

• Duyệt qua tất cả các xâu ~S_i~ với ~1 \leq i \leq N~.

• Một xâu ~S_i~ được xem là thỏa mãn nếu:

  • Độ dài của ~S_i~ thỏa mãn điều kiện: $$\text{len}(S_i) \geq \max(\text{len}(P), \text{len}(Q))$$

  • Giá trị Hash của đoạn đầu ~S_i~ (từ ký tự đầu tiên đến ký tự thứ ~\text{len}(P)~) bằng giá trị Hash của ~P~: $$\text{Hash}(S_i[1, \text{len}(P)]) = \text{Hash}(P)$$

  • Giá trị Hash của đoạn cuối ~S_i~ (từ ký tự thứ ~\text{len}(S_i) - \text{len}(Q) + 1~ đến ký tự cuối cùng) bằng giá trị Hash của ~Q~: $$\text{Hash}(S_i[\text{len}(S_i) - \text{len}(Q) + 1, \text{len}(S_i)]) = \text{Hash}(Q)$$

Độ phức tạp:

• Khởi tạo mảng Hash cho tất cả các xâu ~S_i~ có độ phức tạp ~\mathcal{O}(\sum |S_i|)~.
• Với mỗi truy vấn, ta cần duyệt qua tất cả các xâu ~S_i~, do đó độ phức tạp cho mỗi truy vấn là ~\mathcal{O}(N)~.
• Tổng độ phức tạp của thuật toán là : ~\mathcal{O}(\sum |S_i| + M \times N)~ với ~M~ là số lượng truy vấn.

Subtask 3

Giả sử ~\Sigma_S, \Sigma_P, \Sigma_Q~ lần lượt là tổng độ dài của tất cả các chuỗi ~S~, ~P~ và ~Q~:

$$\Sigma_S = |S_1| + \dots + |S_N|, \quad \Sigma_P = |P_1| + \dots + |P_M|, \quad \Sigma_Q = |Q_1| + \dots + |Q_M|.$$

Chúng ta thấy rằng bài toán này trở nên đơn giản hơn đáng kể nếu có thể bỏ qua ~P~ hoặc ~Q~. Bây giờ, hãy xem xét thuật toán sau:

• Với mỗi ~j~, chỉ trích xuất các chuỗi RNA mà ~|Q_j|~ ký tự cuối cùng là ~Q_j~. Sau đó, đếm số lượng chuỗi RNA được trích xuất mà ~|P_j|~ ký tự đầu tiên là ~P_j~.

Phần sau của thuật toán có thể thực hiện bằng cây Trie. Phần đầu tiên cũng có thể thực hiện bằng Trie. Tuy nhiên, thuật toán này không hiệu quả vì có thể tất cả các chuỗi RNA đều được trích xuất và lưu vào Trie cho mỗi ~j~. Trong trường hợp này, độ phức tạp là ~\mathcal{O}(M \Sigma_S)~. Nhưng ta có thể thêm một tối ưu hóa nhỏ:

• Chỉ trích xuất chuỗi RNA một lần đối với cùng một ~Q~.

Thực tế, điều này giúp giảm đáng kể độ phức tạp xuống:

$$\mathcal{O}(\Sigma_S \sqrt{\Sigma_Q} + \Sigma_P + \Sigma_Q).$$

Dưới đây là chứng minh. Với mỗi ~i~, ~S_i~ chỉ được trích xuất nếu ~Q_j~ là hậu tố của ~S_i~ (tức là ~|Q_j|~ ký tự cuối cùng của ~S_i~ trùng với ~Q_j~). Gọi ~L~ là tập hợp của các ~Q_j~ như vậy. Mỗi chuỗi trong ~L~ có độ dài khác nhau, do đó:

$$\sum_{X \in L} |X| \geq 1 + \dots + \#L = \frac{(\#L + 1) \#L}{2}.$$

Ngoài ra, vì ~\sum_{X \in L} |X| \leq \Sigma_Q~, ta có:

$$\frac{(\#L + 1) \#L}{2} \leq \Sigma_Q.$$

Do đó, ~\#L = \mathcal{O}(\sqrt{\Sigma_Q})~. Điều này có nghĩa là mỗi ~S_i~ chỉ được thêm vào Trie ~\mathcal{O}(\sqrt{\Sigma_Q})~ lần. Thêm một chuỗi ~S_i~ vào Trie mất ~\mathcal{O}(|S_i|)~. Vì vậy, tổng thời gian thêm vào Trie là ~\mathcal{O}(\Sigma_S \sqrt{\Sigma_Q})~.

Bây giờ, vì ta đã có Trie, việc tính toán kết quả có thể thực hiện bằng cách truy cập nút ~P_j~ trong Trie, mất ~\mathcal{O}(\Sigma_P)~. Ngoài ra, việc kiểm tra tất cả các ~Q_1, \dots, Q_M~ mất ~\mathcal{O}(\Sigma_Q)~.

Cuối cùng, ta chứng minh được rằng thuật toán này có độ phức tạp:

$$\mathcal{O}(\Sigma_S \sqrt{\Sigma_Q} + \Sigma_P + \Sigma_Q).$$

Subtask 4

Để giải quyết bài toán này, chúng ta thực hiện các bước sau:
Bước 1: Sắp xếp các xâu RNA theo thứ tự từ điển.

Trước tiên, chúng ta sắp xếp xâu theo thứ tự từ điển. Điều này giúp chúng ta dễ dàng xây dựng một cây Trie, trong đó mỗi nút lưu trữ chỉ số của xâu nhỏ nhất và lớn nhất đi qua nó. Vì các xâu đã được sắp xếp trước, nếu một nút được đi qua bởi xâu thứ ~i~ và xâu thứ ~j~ ~(i \le j)~, thì toàn bộ đoạn chỉ số ~[i, j]~ cũng sẽ đi qua nút đó.
Bước 2: Xây dựng Trie tiền tố và Trie hậu tố.

Sau khi sắp xếp các xâu, chúng ta xây dựng hai cấu trúc Trie:

• Trie tiền tố: Mỗi nút trong Trie này lưu trữ chỉ số của xâu nhỏ nhất và lớn nhất đi qua nó.

• Trie hậu tố: Mỗi nút trong Trie này lưu một tập hợp các chỉ số của các xâu đi qua nó.

Bước 3: Tìm kiếm nhị phân trên Trie hậu tố.

Khi cần đếm số xâu thỏa mãn điều kiện của bài toán, chúng ta có thể thực hiện tìm kiếm nhị phân trên Trie hậu tố để nhanh chóng số xâu RNA phù hợp.

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define MASK(i) ((1) << (i))
#define all(x) x.begin(), x.end()
#define BIT(x, i) ((x) >> (i) & 1)
#define dbg(...) cerr << "#" << __LINE__ << ":[" << #__VA_ARGS__ \
<< "] = [" ,DBG(__VA_ARGS__)

string to_string(const string& s) { return '"' + s + '"'; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
        cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...);
}

template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b, 1) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b, 1) : 0); }

const int MAXN = 1e5 + 6;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int n, m;
int code[256];
string S[MAXN];

class Trie {
private:
    struct data {
        data *nxt[4];
        int minID, maxID;

        data () {
            for (int i = 0; i < 4; i++) nxt[i] = NULL;
            minID = INF;
            maxID = 0;
        }
    };

public: 
    data *p = new data();

    void add(const string &A, const int &ID) {
        data *u = p;
        for (int i = 0; i < sz(A); i++) {
            int k = code[A[i]];
            if (u->nxt[k] == NULL) u->nxt[k] = new data();
            u = u->nxt[k];

            minimize(u->minID, ID);
            maximize(u->maxID, ID);
        }
    }

    pair<int, int> get(const string &A) {
        data *u = p;
        for (int i = 0; i < sz(A); i++) {
            int k = code[A[i]];
            if (u->nxt[k] == NULL) return {-1, -1};
            u = u->nxt[k];
        }   
        return {u->minID, u->maxID};
    }
};

class ReverseTrie {
private:
    struct data {
        data *nxt[4];
        vector<int> setIDS;

        data () {
            for (int i = 0; i < 4; i++) nxt[i] = 0;
        }
    };

public:
    data *p = new data();

    void add(const string &A, const int &ID) {
        data *u = p;
        for (int i = sz(A) - 1; i >= 0; i--) {
            int k = code[A[i]];
            if (u->nxt[k] == NULL) u->nxt[k] = new data();
            u = u->nxt[k];

            u->setIDS.push_back(ID);
        }
    }

    int get(const string &A, int L, int R) {
        data *u = p;
        for (int i = sz(A) - 1; i >= 0; i--) {
            int k = code[A[i]];
            if (u->nxt[k] == NULL) return 0;
            u = u->nxt[k];
        }

        return upper_bound(all(u->setIDS), R) - lower_bound(all(u->setIDS), L);
    }
};

void solve() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) cin >> S[i];

    code['A'] = 0;
    code['U'] = 1;
    code['G'] = 2;
    code['C'] = 3;
    sort(S + 1, S + n + 1);

    Trie tree1;
    ReverseTrie tree2;

    for (int i = 1; i <= n; i++) {
        tree1.add(S[i], i);
        tree2.add(S[i], i);
    }

    for (int i = 1; i <= m; i++) {
        string P, Q;

        cin >> P >> Q;

        pair<int, int> seg = tree1.get(P);
        cout << tree2.get(Q, seg.first, seg.second) << '\n';
    }
}

#define TASK "RNA"
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //#ifndef ONLINE_JUDGE
    freopen(TASK".inp", "r", stdin);
    freopen(TASK".out", "w", stdout);
    //#endif

    int ntest = 1;
    //cin >> ntest;
    while (ntest--) solve();

    return 0;
}
// DP_612