Contest về Trie

Bạn được cho một xâu độ dài \(n\) và một từ điển chứa \(k\) từ. Bạn có thể tạo xâu bằng các từ theo nhiêu cách?

Input

• Dòng đầu vào đầu tiên có một xâu chứa \(n\) kí tự giữa a - z
• Dòng thứ hai có một số nguyên \(k\): số từ trong từ điển
• Cuối cùng là \(k\) dòng mô tả các từ. Mỗi từ là duy nhất và bao gồm các ký tự a - z

Output

• In số cách chia lấy dư cho \(10^9 + 7\)

Constraints

• \(1 \leq n \leq 5000\)
• \(1 \leq k \leq 10^5\)
• Tổng độ dài của các từ tối đa là \(10^6\)

Example

ababc
4
ab
abab
c
cb

2

Cho một danh sách các số điện thoại, hãy xác định danh sách này có số điện thoại nào là phần trước của số khác hay không? Nếu không thì danh sách này được gọi là nhất quán. Giả sử một danh sách có chứa các số điện thoại sau:

• Số khẩn cấp: 911
• Số của Alice: 97625999
• Số của Bob: 91125426
  Trong trường hợp này, ta không thể gọi cho Bob vì tổng đài sẽ kết nối bạn với đường dây khẩn cấp ngay khi bạn quay 3 số đầu trong số của Bob, vì vậy danh sách này là không nhất quán.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên \(1 ≤ t ≤ 40\) là số lượng bộ test.
• Mỗi bộ test sẽ bắt đầu với số lượng số điện thoại \(n\) được ghi trên một dòng, \(1 ≤ n ≤ 10000.\)
• Sau đó là \(n\) dòng, mỗi dòng ghi duy nhất 1 số điện thoại. Một số điện thoại là một dãy không quá 10 chữ số.

Dữ liệu ra

• Với mỗi bộ dữ liệu vào, in ra “YES” nếu danh sách nhất quán và “NO” trong trường hợp ngược lại.

Input

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

Output

NO
YES

Nguồn: CD DHBB 2021

Cho một tập hợp n mẫu DNA, trong đó mỗi mẫu là một chuỗi chứa các ký tự từ \({A, C, G, T}\), chúng ta đang cố gắng tìm một tập hợp con các mẫu trong tập hợp, trong đó độ dài của tiền tố chung dài nhất nhân với số lượng mẫu trong tập con đó là tối đa.
Để cụ thể, hãy để các mẫu là:

1. \(ACGT\)
2. \(ACGTGCGT\)
3. \(ACCGTGC\)
4. \(ACGCCGT\)

Nếu lấy tập con {\(ACGT\)} thì kết quả là \(4 (4 * 1)\), nếu lấy {\(ACGT, ACGTGCGT, ACGCCGT\)} thì kết quả là \(3 * 3 = 9\) (vì ACG là tiền tố chung), nếu lấy {\(ACGT, ACGTGCGT, ACCGTGC, ACGCCGT\)} thì kết quả là \(2 * 4 = 8\).

Bây giờ nhiệm vụ của bạn là báo cáo kết quả tối đa mà chúng ta có thể nhận được từ các mẫu.

Dữ liệu vào

• Dòng đầu là số nguyên \(T (T≤ 10)\), biểu thị số lượng trường hợp thử nghiệm.
• Mỗi trường hợp bắt đầu bằng một dòng chứa số nguyên \(n (1 ≤ n ≤ 50000)\) biểu thị số lượng mẫu DNA.
• Mỗi dòng trong số \(n\) dòng tiếp theo chứa một chuỗi không rỗng có độ dài không lớn hơn 50. Và các chuỗi chứa các ký tự từ \({A, C, G, T}\).

Dữ liệu ra

• Đối với mỗi trường hợp, in số trường hợp và kết quả tối đa có thể nhận được.

Input

3
4
ACGT
ACGTGCGT
ACCGTGC
ACGCCGT
3
CGCGCGCGCGCGCCCCGCCCGCGC
CGCGCGCGCGCGCCCCGCCCGCAC
CGCGCGCGCGCGCCCCGCCCGCTC
2
CGCGCCGCGCGCGCGCGCGC
GGCGCCGCGCGCGCGCGCTC

Output

Case 1: 9
Case 2: 66
Case 3: 20

Nguồn: CD DHBB 2021

Cho dãy \(n\) số nguyên không âm \(a_1, a_2, a_3, ...a_N\) . Gọi giá trị hòa hợp của một cặp hai số (\(a_i , a_j\)) với \(i<j\) được tính bằng \(a_i\ \text{XOR}\ a_j\)

Yêu cầu: Hãy tìm giá trị hòa hợp lớn nhất trong tất cả các cặp.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(T\ (T<10)\) là số bộ dữ liệu;
• Tiếp theo là \(T\) dòng, mỗi dòng tương ứng với một bộ dữ liệu, số đầu tiên là số \(n (n\le 10^5)\), tiếp theo là \(n\) số nguyên không âm \(a_1, a_2, a_3, ...a_N (0\le a_i \le 10^9)\)

Dữ liệu ra

• Gồm \(T\) dòng, mỗi dòng chứa một số là giá trị hòa hợp lớn nhất tìm được tương ứng với bộ dữ liệu vào.

Input

2
3 1 2 3
3 2 4 6

Output

3
6

Nguồn: CD DHBB 2021

Khi học về xâu kí tự, để luyện tập thêm về nội dung này, An và Bình cùng nhau chơi một trò chơi với các xâu kí tự như sau:

• An tạo ra \(n\) xâu kí tự ngẫu nhiên, sau đó, mỗi xâu ban đầu tạo ra một xâu mới bằng cách sao chép một đoạn đầu (hoặc toàn bộ) của xâu đó để tạo thêm được \(n\) xâu nữa.
• Với \(2n\) xâu mà An tạo ra và được đánh số theo thứ tự ngẫu nhiên từ \(1\) đến \(2n\), Bình cần đưa ra một phương án để giải thích cách tạo xâu của An.

Yêu cầu: Cho \(2n\) xâu, hãy chia \(2n\) xâu thành \(n\) nhóm, mỗi nhóm gồm hai xâu mà xâu này là đoạn đầu (tiền tố - prefix) của xâu kia hoặc ngược lại.

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Tiếp theo là \(2n\) dòng, mỗi dòng là một xâu chỉ gồm các kí tự a đến z.

Output

• Gồm \(n\) dòng, mỗi dòng chứa hai số là chỉ số của hai xâu được ghép vào cùng một nhóm.

Constraints

• Tổng số kí tự trong tất cả các xâu không vượt quá \(10^6\).
• Subtask 1: \(n \le 10\).
• Subtask 2: Không có giới hạn nào thêm.

Example

2
ab
adc
a
adce

1 3
4 2