Chuỗi Nguyên Tố

Nguồn: Bài tập do bạn đọc gửi Độ khó: Dễ Mảng đánh dấu Số nguyên tố Xâu

Đề bài

B. CHUỖI NGUYÊN TỐ

Farmerboy vừa mới học về Chuỗi nguyên tố. Một chuỗi gọi là chuỗi nguyên tố khi số các kí tự alphabet khác nhau của chuỗi là số nguyên tố và số lần xuất hiện của mỗi ký tự alphabet là số nguyên tố. Cho một chuỗi, xác định nó có phải là chuỗi nguyên tố hay không.

Input: Dòng 1 gồm 1 số nguyên $T$ là số test. $T$ dòng tiếp theo mỗi dòng là chuỗi $S$ cần phải xác định. Các ký tự trong chuỗi từ 'a' đến 'z'.

Output: In ra $T$ dòng ứng với mỗi test, in ra YES nếu chuỗi là Chuỗi nguyên tố, ngược lại in ra NO.

Giới hạn:

• $1 \le T \le 10$
• $1 \le$ Độ dài chuỗi $\le 100000$
• Thời gian: 1 giây.

Ví dụ – input

2
ababb
abcab

Ví dụ – output

YES
NO

Giải thích:

• Test 1: có 2 ký tự khác nhau xuất hiện (a, b), kí tự a xuất hiện 2 lần, b xuất hiện 3 lần nên in ra YES.
• Test 2: có 3 ký tự khác nhau xuất hiện (a, b, c), a xuất hiện 2 lần, b xuất hiện 2 lần, tuy nhiên c xuất hiện 1 lần (không nguyên tố) nên in ra NO.

Lời mở đầu

Nay mình đi comment dạo thấy bài này thú vị nè: một bạn hỏi vì đề chỉ cho giới hạn thời gian 1 giây nên chưa biết làm sao cho kịp. Bài này nếu biết kỹ thuật mảng đánh dấu thì sẽ rất "khoẻ", còn không biết thì sẽ phải loay hoay với việc thống kê số lần xuất hiện của từng ký tự. Mình viết lại lời giải chi tiết để anh em tham khảo nha 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Tóm lại một chuỗi là "chuỗi nguyên tố" khi thoả cả hai điều kiện:

1. Mỗi ký tự có mặt trong chuỗi đều xuất hiện một số nguyên tố lần (2, 3, 5, 7, 11, ...).
2. Số ký tự khác nhau của chuỗi cũng là số nguyên tố.

Ví dụ ababb: a xuất hiện 2 lần, b 3 lần (đều nguyên tố), có 2 ký tự khác nhau (nguyên tố) ⇒ YES. Còn abcab thì c chỉ xuất hiện 1 lần, mà 1 không phải số nguyên tố ⇒ NO. Lưu ý chuỗi aa cũng là NO nha: a xuất hiện 2 lần thì ổn, nhưng chỉ có 1 ký tự khác nhau, mà 1 không nguyên tố.

Lộ trình lời giải, bấm vào để nhảy tới:

Cách 1Mảng đánh dấu 26 phần tử + kiểm tra nguyên tố đến căn · O(T · N)

Cách 1Mảng đánh dấu + kiểm tra nguyên tố tối ưu – O(T · N)

Những hướng dễ bị TLE

Phần khó của bài là thống kê số lần xuất hiện của từng ký tự phân biệt và đếm có bao nhiêu ký tự phân biệt. Có mấy hướng anh em hay nghĩ tới:

• Làm 2 vòng lặp lồng nhau, xét tất cả các cặp để đếm ⇒ $O(N^2)$ với $N$ là độ dài chuỗi. Với $N = 10^5$ là $10^{10}$ phép tính ⇒ chắc chắn TLE.
• Sắp xếp chuỗi tăng dần để gom các ký tự giống nhau nằm cạnh nhau, sau đó duyệt một lần là thống kê được trong $O(N)$. Nhưng bước sắp xếp kể cả dùng thuật toán tối ưu thì cũng mất $O(N \log N)$.

Giải pháp tốt nhất là dùng mảng đánh dấu, độ phức tạp chỉ $O(N)$.

Mảng đánh dấu 26 phần tử

Ta tạo mảng số nguyên a gồm 26 phần tử (ứng với 26 chữ cái từ a đến z), ban đầu tất cả bằng 0. a[0] là số lần xuất hiện của ký tự a, a[1] là của b, cứ thế a[2], a[3], a[4], ... là của c, d, e, ...

Duyệt chuỗi, với mỗi ký tự s[i] thì làm a[s[i] - 'a']++. Được như vậy là vì bản chất ký tự trong C/C++ được biểu diễn bằng mã ASCII là các số nguyên: 'a' có mã 97, 'b' là 98, 'c' là 99, ... Nên khi s[i] = 'a' thì s[i] - 'a' hiểu là $97 - 97 = 0$; khi s[i] = 'b' thì là $98 - 97 = 1$. Viết a[s[i] - 97]++ cũng được.

Thuật toán

1. Duyệt chuỗi một lần: a[s[i] - 'a']++ ⇒ có số lần xuất hiện của từng ký tự.
2. Đặt cờ hiệu check = true (giả định chuỗi hợp lệ), biến đếm cnt = 0.
3. Duyệt 26 phần tử của a: với a[i] ≠ 0 (ký tự có xuất hiện) thì cnt++, rồi kiểm tra a[i] có nguyên tố không; nếu không thì check = false và break luôn, không cần xét tiếp.
4. Sau vòng lặp, kiểm tra cnt (số ký tự phân biệt) có nguyên tố không; nếu không thì check = false.
5. check còn true thì in YES, ngược lại in NO.

Kiểm tra số nguyên tố đến căn bậc 2

Bước kiểm tra một số $x$ có nguyên tố hay không thì nên dùng cách tối ưu: chỉ thử các ước $i$ với $i \cdot i \le x$, độ phức tạp $O(\sqrt{x})$. Nếu $x$ có ước $d$ lớn hơn $\sqrt{x}$ thì nó cũng có ước $x / d$ nhỏ hơn $\sqrt{x}$, nên thử tới căn là đủ. Cuối hàm trả về x >= 2 để loại luôn 0 và 1.

Minh hoạ

Em nhập một chuỗi (chữ thường) rồi bấm Tiếp để xem: đầu tiên đếm từng ký tự vào mảng a, sau đó xét từng ô khác 0 xem có nguyên tố không, cuối cùng xét số ký tự phân biệt:

S

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int x){
    for(int i = 2; i * i <= x; ++i){
        if(x % i == 0){
            return false;
        }
    }
    return x >= 2;
}

int main(){
    int t;
    cin >> t;
    string s;
    while(t--){
        cin >> s;
        int a[26] = {0};
        for(int i = 0; i < (int)s.length(); ++i){
            a[s[i] - 'a']++;
        }
        bool check = true;
        int cnt = 0;
        for(int i = 0; i < 26; ++i){
            if(a[i]){
                cnt++;
                if(!isPrime(a[i])){
                    check = false;
                    break;
                }
            }
        }
        if(!isPrime(cnt)){
            check = false;
        }
        if(check){
            cout << "YES\n";
        }
        else{
            cout << "NO\n";
        }
    }
    return 0;
}

import sys


def is_prime(x):
    i = 2
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return x >= 2


def main():
    data = sys.stdin.read().split()
    t = int(data[0])
    res = []
    for k in range(1, t + 1):
        s = data[k]
        a = [0] * 26
        for c in s:
            a[ord(c) - ord('a')] += 1
        check = True
        cnt = 0
        for i in range(26):
            if a[i]:
                cnt += 1
                if not is_prime(a[i]):
                    check = False
                    break
        if not is_prime(cnt):
            check = False
        res.append("YES" if check else "NO")
    print("\n".join(res))


main()

Nhớ khởi tạo lại mảng đếm cho mỗi test

Bài có nhiều test, nên mảng a phải được đưa về 0 ở đầu mỗi test. Trong code gốc mình gõ trên điện thoại, mình lỡ khai báo int a[26] = {0}; ở ngoài vòng while nên số lần đếm của test trước bị cộng dồn sang test sau. Test đề vẫn ra đúng do trùng hợp (test 2 vẫn là NO), nhưng ví dụ với 2 test cùng là aabbb thì test thứ hai sẽ đếm thành a = 4, b = 6 và in sai NO. Code ở trên đã đưa khai báo vào trong vòng lặp (dòng 19) nha anh em.

C++▶ Chạy tay từng dòng codeĐếm bằng mảng a[26], rồi kiểm tra từng số lần xuất hiện và số ký tự phân biệt có nguyên tố không.

Dữ liệu vào (stdin) – sửa thoải mái2 ababb abcab

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4bool isPrime(int x){

5 for(int i = 2; i * i <= x; ++i){

6 if(x % i == 0){

7 return false;

8 }

9 }

10 return x >= 2;

11}

12

13int main(){

14 int t;

15 cin >> t;

16 string s;

17 while(t--){

18 cin >> s;

19 int a[26] = {0};

20 for(int i = 0; i < (int)s.length(); ++i){

21 a[s[i] - 'a']++;

22 }

23 bool check = true;

24 int cnt = 0;

25 for(int i = 0; i < 26; ++i){

26 if(a[i]){

27 cnt++;

28 if(!isPrime(a[i])){

29 check = false;

30 break;

31 }

32 }

33 }

34 if(!isPrime(cnt)){

35 check = false;

36 }

37 if(check){

38 cout << "YES\n";

39 }

40 else{

41 cout << "NO\n";

42 }

43 }

44 return 0;

45}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: chuỗi $S$ cỡ $N$ và mảng đánh dấu chỉ 26 phần tử ⇒ $O(N)$ (bộ nhớ phụ chỉ $O(26)$).
• Thời gian: mỗi test duyệt chuỗi một lần $O(N)$, rồi kiểm tra nguyên tố tối đa 26 giá trị $a[i]$ và thêm biến đếm $cnt$, mỗi lần $O(\sqrt{N})$. Tổng quát là $O(T \cdot (N + 27\sqrt{N}))$ (27 là vì 26 phần tử của mảng $a$ cộng thêm biến đếm sau cùng). Trường hợp xấu nhất $T = 10$, $N = 10^5$: $10 \cdot (10^5 + 27 \cdot 317) \approx 10^6$ phép tính, giới hạn 1 giây vẫn ổn nhé (ngưỡng an toàn cho 1 giây cỡ $(3$ đến $5) \cdot 10^7$).

Không gian$O(N)$

Thời gian$O(T \cdot N)$

Chuyên mục dự đoán trước kết quả 😆

• Vẫn dùng mảng đánh dấu nhưng kiểm tra số nguyên tố kiểu tệ nhất $O(x)$ thì vẫn AC được, vì lúc này là $O(T \cdot (N + 27N))$ cỡ $3 \cdot 10^7$ – nhưng đã tiệm cận giới hạn nên cũng hên xui nha.
• Không dùng mảng đánh dấu mà sắp xếp với thuật $O(N \log N)$: nếu kiểm tra nguyên tố tối ưu thì vẫn có thể AC, còn kiểm tra không tối ưu thì hên xui, mà chắc xui nhiều hơn hên.
• Dùng 2 vòng lặp lồng nhau xét mọi cặp, hoặc sắp xếp kiểu $O(N^2)$ thì chắc chắn TLE với giới hạn đề đã cho.

Ghi chú của mình: code C++ và Python ở trên đã được kiểm tra với 500 bộ test ngẫu nhiên (mỗi bộ đến 10 chuỗi, có cả chuỗi chỉ 1 loại ký tự), so với code vét cạn dùng Counter – khớp hết. Với $T = 10$, mỗi chuỗi dài $10^5$: bản C++ chạy khoảng 0.03 giây, bản Python khoảng 0.12 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇