Khóa học CTDL và GT

Bài 10.2. Kỹ thuật xử lý chuỗi hiệu quả

Chuỗi (string) là một trong những kiểu dữ liệu phổ biến và quan trọng nhất trong lập trình. Chúng ta sử dụng chuỗi để lưu trữ tên, văn bản, dữ liệu từ file, thông tin mạng, và vô vàn các loại dữ liệu dạng văn bản khác. Tuy nhiên, việc xử lý chuỗi không hiệu quả có thể trở thành điểm nghẽn (bottleneck) nghiêm trọng cho hiệu năng ứng dụng của bạn, đặc biệt khi làm việc với các chuỗi lớn hoặc thực hiện các thao tác lặp đi lặp lại.

Trong bài viết này, chúng ta sẽ đi sâu vào kỹ thuật xử lý chuỗi hiệu quả, tập trung vào việc làm thế nào để thao tác với chuỗi trong C++ (và các ngôn ngữ khác có cơ chế tương tự) một cách tối ưu nhất về thời gian và bộ nhớ. Chúng ta sẽ khám phá các phương pháp thông minh hơn là chỉ dùng các thao tác cơ bản một cách ngẫu nhiên.

1. Hiểu Rõ Về std::string và Chi Phí Ngầm

Trong C++, std::string là lớp cung cấp khả năng quản lý chuỗi động. Điều quan trọng cần nhớ là khi bạn thực hiện một số thao tác nhất định, std::string có thể tạo ra các bản sao (copy) của dữ liệu chuỗi ngầm bên trong. Việc tạo bản sao này tốn kém cả về thời gian (để sao chép từng ký tự) và bộ nhớ (để cấp phát không gian mới).

Các thao tác có khả năng tạo bản sao hoặc yêu cầu cấp phát lại bộ nhớ bao gồm:

• Phép gán (=).
• Truyền chuỗi theo giá trị vào hàm.
• Trả về chuỗi từ hàm theo giá trị.
• Các thao tác nối chuỗi (+).
• Trích xuất chuỗi con (substr).
• Thay đổi kích thước chuỗi (khi dung lượng hiện tại không đủ).

Mục tiêu của xử lý chuỗi hiệu quả là giảm thiểu những chi phí ngầm này whenever possible.

2. Truy Cập và Duyệt Chuỗi: Thường Hiệu Quả

Các thao tác truy cập từng ký tự hoặc duyệt qua chuỗi thường rất hiệu quả.

• Truy cập ngẫu nhiên: Sử dụng toán tử [] hoặc phương thức .at() để truy cập ký tự tại một chỉ mục cụ thể. Cả hai đều là thao tác O(1) (thời gian hằng số), giả sử chỉ mục hợp lệ. .at() cung cấp kiểm tra giới hạn (bounds checking) và ném ngoại lệ nếu chỉ mục không hợp lệ, trong khi [] thì không.
• Duyệt tuần tự: Sử dụng vòng lặp for dựa trên phạm vi (range-based for loop) hoặc iterator.

#include <iostream>
#include <string>
#include <vector> // Example usage with vector of strings

int main() {
    std::string text = "Xin chao FullhouseDev!";

    // Truy cap ky tu theo chi muc (O(1))
    std::cout << "Ky tu dau tien: " << text[0] << std::endl;
    std::cout << "Ky tu cuoi cung: " << text.back() << std::endl; // .back() cung O(1)

    // Duyet chuoi bang vong lap range-based for (Hieu qua)
    std::cout << "Duyet bang range-based for: ";
    for (char c : text) {
        std::cout << c << " ";
    }
    std::cout << std::endl;

    // Duyet chuoi bang iterator (Hieu qua, linh hoat hon trong mot so truong hop)
    std::cout << "Duyet bang iterator: ";
    for (auto it = text.begin(); it != text.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

Giải thích: Các cách truy cập và duyệt này rất cơ bản và thường không phải là nguồn gốc của sự thiếu hiệu quả, trừ khi bạn thực hiện các thao tác bên trong vòng lặp mà lại tốn kém (ví dụ: liên tục tạo chuỗi con).

3. Tìm Kiếm (Searching): Sử Dụng Công Cụ Có Sẵn

Khi cần tìm một chuỗi con hoặc một ký tự trong chuỗi, thư viện chuẩn của C++ cung cấp các phương thức find(), rfind(), find_first_of(), find_last_of(), find_first_not_of(), find_last_not_of(). Các phương thức này thường được tối ưu hóa cao độ.

• Sử dụng string::find(): Tìm lần xuất hiện đầu tiên của chuỗi con hoặc ký tự.
• Sử dụng string::rfind(): Tìm lần xuất hiện cuối cùng.

Tránh việc tự viết thuật toán tìm kiếm đơn giản (naive search) trong hầu hết các trường hợp, vì các thuật toán trong thư viện chuẩn (có thể dựa trên Boyer-Moore hoặc các biến thể được tối ưu) thường nhanh hơn đáng kể, đặc biệt trên các chuỗi dài.

#include <iostream>
#include <string>

int main() {
    std::string sentence = "Lap trinh C++ rat thu vi, C++ la ngon ngu manh me.";
    std::string search_term = "C++";
    std::string characters_to_find = "aeiou"; // Tim ky tu trong tap hop

    // Tim lan xuat hien dau tien
    size_t pos_first = sentence.find(search_term);
    if (pos_first != std::string::npos) {
        std::cout << "Tim thay '" << search_term << "' lan dau tai vi tri: " << pos_first << std::endl;
    } else {
        std::cout << "'" << search_term << "' khong tim thay." << std::endl;
    }

    // Tim lan xuat hien cuoi cung
    size_t pos_last = sentence.rfind(search_term);
    if (pos_last != std::string::npos) {
        std::cout << "Tim thay '" << search_term << "' lan cuoi tai vi tri: " << pos_last << std::endl;
    }

    // Tim ky tu bat ky trong tap hop (lan xuat hien dau tien)
    size_t pos_vowel = sentence.find_first_of(characters_to_find);
    if (pos_vowel != std::string::npos) {
         std::cout << "Ky tu nguyen am dau tien tim thay tai vi tri: " << pos_vowel << " ('" << sentence[pos_vowel] << "')" << std::endl;
    }

    return 0;
}

Giải thích: Các phương thức find, rfind, v.v., được thiết kế để hiệu quả. std::string::npos là một giá trị đặc biệt (thường là giá trị lớn nhất của size_t) biểu thị việc không tìm thấy. Luôn sử dụng nó để kiểm tra kết quả tìm kiếm.

4. Thay Đổi và Chỉnh Sửa Chuỗi: Đây Mới Là Nơi Cần Cẩn Thận!

Các thao tác thay đổi chuỗi như thêm, xoá, chèn, thay thế, và trích xuất chuỗi con là những nơi tiềm ẩn chi phí lớn nhất nếu không được sử dụng cẩn thận.

4.1. Trích Xuất Chuỗi Con (substr)

substr(pos, len) tạo ra một chuỗi mới chứa các ký tự từ pos với độ dài len. Điều này có nghĩa là nó cấp phát bộ nhớ mới và sao chép dữ liệu. Thực hiện substr trong vòng lặp trên một chuỗi lớn có thể cực kỳ tốn kém.

#include <iostream>
#include <string>
#include <vector>

int main() {
    std::string data = "value1,value2,value3,value4,value5";
    std::string delimiter = ",";
    size_t pos = 0;
    std::vector<std::string> tokens;

    // Cach THIEU hieu qua (dung substr nhieu lan)
    // Vong lap nay lien tuc tao ra chuoi con moi
    std::cout << "Phan tich chuoi (kem hieu qua voi substr):" << std::endl;
    std::string temp_data = data; // Tao ban sao de khong thay doi 'data' goc
    while ((pos = temp_data.find(delimiter)) != std::string::npos) {
        tokens.push_back(temp_data.substr(0, pos)); // Tao chuoi con dau tien
        temp_data.erase(0, pos + delimiter.length()); // Xoa phan da xu ly (co the ton kem)
    }
    tokens.push_back(temp_data); // Lay phan con lai

    for (const auto& token : tokens) {
        std::cout << token << std::endl;
    }

    // Cach HIEU QUA hon (xu ly bang chi muc hoac iterator)
    // Thay vi tao chuoi con moi, chi theo doi vi tri bat dau va ket thuc
    std::cout << "\nPhan tich chuoi (hieu qua hon voi chi muc):" << std::endl;
    tokens.clear(); // Xoa du lieu cu
    size_t start = 0;
    size_t end = data.find(delimiter);
    while (end != std::string::npos) {
        // Tao chuoi con chi mot lan sau khi tim thay diem ket thuc
        tokens.push_back(data.substr(start, end - start));
        start = end + delimiter.length();
        end = data.find(delimiter, start); // Tim tu vi tri 'start'
    }
    // Them phan con lai sau ky tu phan cach cuoi cung
    tokens.push_back(data.substr(start, data.length() - start));

    for (const auto& token : tokens) {
        std::cout << token << std::endl;
    }

    return 0;
}

Giải thích: Ví dụ trên minh họa sự khác biệt. Cách thứ nhất liên tục tạo chuỗi con và xoá bớt chuỗi ban đầu (xoá cũng là thao tác có thể tốn kém). Cách thứ hai hiệu quả hơn bằng cách chỉ sử dụng các chỉ mục (start, end) để xác định vị trí các phần tử cần tách, và chỉ tạo chuỗi con một lần cho mỗi phần tử khi đã xác định được phạm vi của nó.

4.2. Nối Chuỗi (Concatenation)

Toán tử + để nối chuỗi cũng tạo ra chuỗi tạm thời. Nối nhiều chuỗi bằng + liên tiếp trong một biểu thức hoặc trong vòng lặp có thể rất chậm.

#include <iostream>
#include <string>
#include <chrono>

int main() {
    std::string base = "Fragment";
    std::string result_bad = "";
    int num_fragments = 10000; // So luong phan can noi

    auto start_bad = std::chrono::high_resolution_clock::now();
    // Cach THIEU hieu qua: Dung '+' trong vong lap
    for (int i = 0; i < num_fragments; ++i) {
        result_bad = result_bad + base; // Tao chuoi moi o moi lan lap
    }
    auto end_bad = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed_bad = end_bad - start_bad;
    // std::cout << "Ket qua kem hieu qua (chi hien thi mot phan): " << result_bad.substr(0, 100) << "..." << std::endl;
    std::cout << "Thoi gian noi chuoi kem hieu qua: " << elapsed_bad.count() << " s" << std::endl;


    std::string result_good = "";
    result_good.reserve(base.length() * num_fragments); // Uoc luong va cap phat truoc

    auto start_good = std::chrono::high_resolution_clock::now();
    // Cach HIEU QUA: Dung append() va reserve()
    for (int i = 0; i < num_fragments; ++i) {
        result_good.append(base); // Hoac result_good += base; - Thuong hieu qua hon '+'
    }
    auto end_good = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed_good = end_good - start_good;
    // std::cout << "Ket qua hieu qua (chi hien thi mot phan): " << result_good.substr(0, 100) << "..." << std::endl;
    std::cout << "Thoi gian noi chuoi hieu qua: " << elapsed_good.count() << " s" << std::endl;


    return 0;
}

Giải thích: Khi nối nhiều chuỗi nhỏ lại với nhau, đặc biệt trong vòng lặp, việc sử dụng result_bad = result_bad + base; tạo ra rất nhiều chuỗi tạm thời. Mỗi lần lặp, một chuỗi mới được tạo ra có kích thước lớn hơn, và nội dung cũ cùng với base được sao chép vào đó. Điều này dẫn đến độ phức tạp thời gian là O(N^2) (với N là tổng chiều dài cuối cùng).

Ngược lại, sử dụng append() (hoặc toán tử +=) cố gắng chỉnh sửa chuỗi tại chỗ. Dù vẫn có thể xảy ra việc cấp phát lại bộ nhớ khi chuỗi vượt quá dung lượng hiện tại, nhưng số lần cấp phát lại ít hơn nhiều và được quản lý theo cấp số nhân (growing exponentially), dẫn đến độ phức tạp trung bình là O(N). Việc sử dụng .reserve() để cấp phát trước bộ nhớ khi bạn có ước tính về kích thước cuối cùng sẽ giúp tránh được hầu hết các lần cấp phát lại, làm cho thao tác append (hoặc +=) hiệu quả gần như O(1) trên mỗi lần nối (amortized constant time), dẫn đến tổng thời gian là O(N).

4.3. replace, insert, erase

Các phương thức này chỉnh sửa chuỗi tại chỗ, nhưng có thể tốn kém vì chúng có thể yêu cầu:

1. Cấp phát lại bộ nhớ: Nếu thao tác làm tăng kích thước chuỗi vượt quá dung lượng hiện tại.
2. Di chuyển dữ liệu: Khi chèn hoặc xoá ở giữa chuỗi, các ký tự sau điểm chèn/xoá cần phải được di chuyển để tạo chỗ trống hoặc lấp đầy khoảng trống. Thao tác này có độ phức tạp O(N) với N là số ký tự cần di chuyển.

#include <iostream>
#include <string>

int main() {
    std::string sentence = "Mot cau van ban don gian.";

    // Thay the mot phan (co the yeu cau di chuyen du lieu)
    sentence.replace(4, 3, "doan"); // Thay "cau" bang "doan" (4 la vi tri, 3 la do dai)
    std::cout << "Sau khi thay the: " << sentence << std::endl; // Output: Mot doan van ban don gian.

    // Chen chuoi (co the yeu cau cap phat lai va di chuyen du lieu)
    sentence.insert(0, "Day la "); // Chen vao dau chuoi
    std::cout << "Sau khi chen: " << sentence << std::endl; // Output: Day la Mot doan van ban don gian.

    // Xoa mot phan (co the yeu cau di chuyen du lieu)
    sentence.erase(0, 7); // Xoa "Day la "
    std::cout << "Sau khi xoa: " << sentence << std::endl; // Output: Mot doan van ban don gian.

    // Xoa ky tu cu the (dung erase-remove idiom - rat hieu qua)
    std::string messy = "string  voi   nhieu     khoang trang";
    // Loai bo tat ca khoang trang
    messy.erase(std::remove(messy.begin(), messy.end(), ' '), messy.end());
    std::cout << "Sau khi xoa khoang trang: " << messy << std::endl; // Output: stringvoinhieukhoangtrang

    return 0;
}

Giải thích: Các thao tác replace, insert, erase theo chỉ mục có thể tốn kém khi áp dụng cho chuỗi lớn hoặc lặp đi lặp lại, đặc biệt là ở các vị trí gần đầu chuỗi, vì nó ảnh hưởng đến phần lớn dữ liệu phía sau.

Kỹ thuật erase-remove idiom sử dụng std::remove (từ <algorithm>) kết hợp với string::erase. std::remove không thực sự xóa các phần tử, mà chỉ di chuyển các phần tử không bị xoá lên đầu phạm vi được chỉ định và trả về một iterator tới vị trí cuối mới. Sau đó, string::erase được gọi với iterator này để cắt bỏ phần dư thừa ở cuối. Kỹ thuật này hiệu quả hơn nhiều so với việc xoá từng ký tự một trong vòng lặp, vì nó thực hiện di chuyển dữ liệu ít hơn đáng kể.

5. Truyền Chuỗi Qua Hàm: Luôn Ưu Tiên Tham Chiếu const&

Một trong những cách đơn giản nhưng cực kỳ quan trọng để xử lý chuỗi hiệu quả là cách bạn truyền chúng vào hàm.

• Truyền theo giá trị: void process(std::string s) - Tạo một bản sao đầy đủ của chuỗi. Tốn kém.
• Truyền theo tham chiếu: void process(std::string& s) - Truyền tham chiếu đến chuỗi gốc. Không tạo bản sao, nhưng hàm có thể thay đổi chuỗi gốc.
• Truyền theo tham chiếu hằng: void process(const std::string& s) - Truyền tham chiếu đến chuỗi gốc. Không tạo bản sao, và hàm không thể thay đổi chuỗi gốc. Đây là cách được khuyến khích cho các hàm chỉ đọc dữ liệu từ chuỗi.

#include <iostream>
#include <string>
#include <chrono>

// Ham nhan chuoi theo gia tri (kem hieu qua cho chuoi lon)
void process_by_value(std::string s) {
    // Chi doc chuoi
    // std::cout << s.length() << std::endl;
}

// Ham nhan chuoi theo tham chieu const (hieu qua)
void process_by_const_ref(const std::string& s) {
    // Chi doc chuoi
    // std::cout << s.length() << std::endl;
}

int main() {
    std::string large_string(100000, 'A'); // Tao mot chuoi lon

    auto start_value = std::chrono::high_resolution_clock::now();
    process_by_value(large_string);
    auto end_value = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed_value = end_value - start_value;
    std::cout << "Thoi gian truyen theo gia tri: " << elapsed_value.count() << " s" << std::endl;

    auto start_ref = std::chrono::high_resolution_clock::now();
    process_by_const_ref(large_string);
    auto end_ref = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed_ref = end_ref - start_ref;
    std::cout << "Thoi gian truyen theo tham chieu const: " << elapsed_ref.count() << " s" << std::endl;

    return 0;
}

Giải thích: Ví dụ trên cho thấy sự khác biệt rõ rệt về thời gian khi truyền một chuỗi lớn. Truyền theo giá trị yêu cầu sao chép toàn bộ chuỗi, trong khi truyền theo tham chiếu hằng chỉ truyền địa chỉ của chuỗi, là một thao tác rất nhanh. Luôn ưu tiên truyền chuỗi theo const std::string& trừ khi bạn thực sự cần sửa đổi bản sao của chuỗi hoặc sửa đổi chuỗi gốc (khi đó dùng std::string&).

6. Sử Dụng String Streams (<sstream>) Cho Phân Tích và Định Dạng Phức Tạp

Khi cần phân tích chuỗi thành các phần tử (ví dụ: tách các số được phân cách bằng dấu phẩy) hoặc xây dựng chuỗi phức tạp từ nhiều kiểu dữ liệu khác nhau, stringstream là một công cụ mạnh mẽ và thường hiệu quả hơn so với việc sử dụng kết hợp substr, find, và nối chuỗi thủ công, đặc biệt khi định dạng có cấu trúc.

stringstream hoạt động giống như luồng nhập/xuất (như cin, cout) nhưng trên bộ nhớ đệm là một chuỗi.

#include <iostream>
#include <string>
#include <sstream>
#include <vector>

int main() {
    std::string data = "ID:123,Name:Alice,Score:95.5";
    std::stringstream ss(data); // Khoi tao stringstream voi chuoi

    std::string segment;
    std::vector<std::string> parts;

    // Phan tich chuoi theo dau phay (dung getline voi delimiter)
    while(std::getline(ss, segment, ',')) {
        parts.push_back(segment);
    }

    std::cout << "Cac phan sau khi phan tich:" << std::endl;
    for (const auto& p : parts) {
        std::cout << p << std::endl;
    }

    // Trich xuat du lieu cu the tu mot phan (dung lai stringstream hoac tao moi)
    if (parts.size() >= 3) {
        std::stringstream ss_id(parts[0]);
        std::string key;
        int id_value;
        std::getline(ss_id, key, ':'); // Lay phan "ID"
        ss_id >> id_value;             // Lay so 123

        std::stringstream ss_score(parts[2]);
        double score_value;
        std::getline(ss_score, key, ':'); // Lay phan "Score"
        ss_score >> score_value;       // Lay so 95.5

        std::cout << "\nTrich xuat du lieu cu the:" << std::endl;
        std::cout << "ID: " << id_value << std::endl;
        std::cout << "Score: " << score_value << std::endl;
    }

    // Xay dung chuoi hieu qua tu cac kieu du lieu khac nhau
    std::stringstream output_ss;
    std::string name = "Bob";
    int age = 30;
    double height = 1.75;

    output_ss << "Ten: " << name << ", Tuoi: " << age << ", Chieu cao: " << height << "m.";
    std::string final_string = output_ss.str(); // Lay chuoi cuoi cung tu stringstream

    std::cout << "\nChuoi xay dung tu stringstream:" << std::endl;
    std::cout << final_string << std::endl;

    return 0;
}

Giải thích: stringstream giúp tách logic phân tích/định dạng khỏi logic thao tác chuỗi cơ bản. Khi bạn chèn (>>) hoặc trích xuất (<<) dữ liệu vào stringstream, nó quản lý bộ nhớ đệm bên trong một cách hiệu quả. Đặc biệt, khi xây dựng một chuỗi lớn từ nhiều phần nhỏ và các kiểu dữ liệu khác nhau, sử dụng stringstream (bằng cách chèn từng phần vào luồng) thường hiệu quả hơn việc liên tục nối chuỗi bằng toán tử +, vì stringstream có thể quản lý việc cấp phát bộ nhớ tốt hơn cho luồng dữ liệu đang được thêm vào. .str() cuối cùng sẽ trả về chuỗi kết quả.

7. Tránh Tạo Chuỗi Tạm Thời Không Cần Thiết

Một nguyên tắc chung là cố gắng tránh tạo ra các chuỗi tạm thời (temporary strings) không cần thiết. Ví dụ:

• Thay vì some_function(my_string + other_string); (tạo chuỗi tạm thời rồi truyền), hãy cân nhắc:

  • my_string += other_string; some_function(my_string); (nếu my_string có thể thay đổi).
  • some_function(my_string, other_string); (nếu hàm some_function có thể nhận nhiều đối số chuỗi hoặc tham chiếu).
  • some_function((my_string + other_string).c_str()); (nếu hàm nhận C-style string và bạn chấp nhận chi phí tạo chuỗi tạm thời).

• Thay vì xử lý my_string.substr(...) liên tục trong vòng lặp, hãy sử dụng các chỉ mục hoặc iterator để làm việc trực tiếp trên chuỗi gốc, như đã minh họa trong ví dụ phân tách chuỗi.

8. Sử Dụng C-style Strings (char*) Khi Phù Hợp (Có Ý Thức)

Mặc dù std::string an toàn và tiện lợi hơn nhiều so với chuỗi C-style (char*), đôi khi làm việc trực tiếp với con trỏ và mảng ký tự có thể mang lại hiệu năng cao hơn trong các trường hợp rất cụ thể, ví dụ khi giao tiếp với các API cũ, hoặc khi bạn cần kiểm soát hoàn toàn việc quản lý bộ nhớ và các thao tác trên mảng bytes thô.

Tuy nhiên, điều này đi kèm với rủi ro quản lý bộ nhớ thủ công (rò rỉ bộ nhớ, lỗi truy cập ngoài giới hạn) và thiếu các tiện ích sẵn có của std::string. Chỉ sử dụng C-style strings khi bạn hiểu rõ mình đang làm gì và có lý do chính đáng về hiệu năng trong một ngữ cảnh cụ thể sau khi đã đo lường.

9. Xem Xét Các Thư Viện Chuyên Biệt

Đối với các tác vụ xử lý chuỗi cực kỳ chuyên sâu và hiệu năng cao (ví dụ: phân tích cú pháp tốc độ cao, xử lý văn bản lớn), có thể có các thư viện chuyên biệt cung cấp các cấu trúc dữ liệu hoặc thuật toán tối ưu hơn cả std::string cho những tác vụ đó (ví dụ: các thư viện xử lý Regular Expression hiệu quả, các thư viện parsing).

Bài tập ví dụ:

[Xâu kí tự].Liệt kê các từ khác nhau trong xâu.

Cho một xâu kí tự S bao gồm các chữ cái và dấu cách,hãy liệt kê các từ khác nhau trong xâu S, đầu tiên hãy liệt kê các từ khác nhau theo thứ tự từ điển tăng dần, sau đó cách một dấu cách rồi liệt kê các từ theo thứ tự xuất hiện trong xâu.

Input Format

Dòng duy nhất chứa xâu S có độ dài không quá 1000 kí tự.

Constraints

.

Output Format

Dòng đầu tiên in ra các trong xâu theo thứ tự từ điển. Dòng thứ hai in ra các từ theo thứ tự xuất hiện trong xâu.

Ví dụ:

Dữ liệu vào

lap   trinh java web java   php web

Dữ liệu ra

java lap php trinh web
lap trinh java web php

Okay, đây là hướng dẫn giải bài tập "Liệt kê các từ khác nhau trong xâu" bằng C++ một cách ngắn gọn, không cung cấp code hoàn chỉnh:

1. Đọc input: Đọc toàn bộ dòng đầu vào vào một biến kiểu std::string (sử dụng getline để đọc cả dòng, bao gồm cả dấu cách).

2. Tách từ: Sử dụng std::stringstream để tách xâu thành các từ riêng lẻ. stringstream tự động xử lý các dấu cách liên tiếp như một dấu phân cách duy nhất.

3. Xử lý từ cho output 1 (thứ tự từ điển): Khi tách được mỗi từ, hãy thêm từ đó vào một std::set<std::string>. std::set tự động lưu trữ các phần tử duy nhất và giữ chúng được sắp xếp theo thứ tự từ điển.

4. Xử lý từ cho output 2 (thứ tự xuất hiện):

   • Sử dụng một std::vector<std::string> để lưu trữ các từ duy nhất theo thứ tự chúng xuất hiện lần đầu.
   • Sử dụng một tập hợp (ví dụ: std::set<std::string> hoặc std::unordered_set<std::string>) làm bộ theo dõi để kiểm tra xem một từ đã được thêm vào vector này chưa.
   • Khi tách được một từ, hãy kiểm tra xem từ đó đã có trong tập hợp theo dõi chưa.
   • Nếu từ đó chưa có trong tập hợp theo dõi, hãy thêm nó vào vector và thêm nó vào tập hợp theo dõi.

5. In kết quả:

   • Duyệt qua std::set (từ bước 3) và in từng từ, cách nhau bởi dấu cách. Sau khi in xong tất cả, in một ký tự xuống dòng.
   • Duyệt qua std::vector (từ bước 4) và in từng từ, cách nhau bởi dấu cách.

Tóm tắt các bước chính và cấu trúc dữ liệu cần dùng:

• Sử dụng getline để đọc xâu.
• Sử dụng stringstream để tách từ.
• Sử dụng std::set<std::string> để lưu trữ các từ duy nhất theo thứ tự từ điển (cho output 1).
• Sử dụng std::vector<std::string> để lưu trữ các từ duy nhất theo thứ tự xuất hiện (cho output 2).
• Sử dụng một std::set<std::string> (hoặc unordered_set) bổ trợ để kiểm tra xem một từ đã được thêm vào vector cho output 2 hay chưa.

Làm thêm nhiều bài tập miễn phí tại đây