10.3K 778 121

Đã đăng vào thg 6 15, 2022 8:54 SA 26 phút đọc

42.9K

Bài 10: Xâu kí tự

I. Dữ liệu dạng văn bản

1. Bảng kí tự ASCII

ASCII - tên đầy đủ là American Standard Code for Information Interchange - là một bảng mã chuẩn trao đổi thông tin Hoa Kỳ, bao gồm các kí tự và mã của chúng dựa trên bảng chữ cái Latin được dùng trong tiếng Anh hiện đại. Bảng mã này bao gồm $256$ kí tự được đánh số hiệu thập phân từ $0$ tới $255,$ thường được dùng để hiển thị văn bản trong máy tính và các thiết bị thông tin khác. Các kí tự mà chúng ta sử dụng trong lập trình đều nằm trong bảng mã này. Để làm việc dễ dàng trên máy tính, mỗi kí tự đều được mã hóa bởi những bit nhị phân $0 - 1$ và quy đổi ra giá trị thập phân tương ứng để người dùng dễ thao tác hơn. Ví dụ, kí tự A có số hiệu thập phân là $65,$ kí tự z có số hiệu là $122,...$

Trong bảng mã ASCII có những kí tự in được và không in được. Trong chương này, chúng ta sẽ làm việc với các kí tự in được, nhiều nhất là các kí tự chữ cái và chữ số. Nếu muốn tìm hiểu kĩ hơn về bảng mã ASCII đầy đủ, bạn đọc có thể truy cập vào đường link sau: https://vi.wikipedia.org/wiki/ASCII

2. Kí tự và xâu kí tự

Trong máy tính, thông tin được biểu diễn ở dạng số và dạng phi số. Chúng ta đã quá quen thuộc với thông tin dạng số, vậy còn dạng phi số? Đó là văn bản, hình ảnh, âm thanh,...Đối với lập trình thi đấu, thông tin dạng văn bản cũng xuất hiện thường xuyên không kém dạng số, và các ngôn ngữ lập trình đều cung cấp những kiểu dữ liệu để lưu trữ thông tin dạng văn bản. Có hai loại dữ liệu dạng văn bản thường gặp nhất là kiểu kí tự và kiểu xâu kí tự (nhiều kí tự ghép lại với nhau).

Đối với kiểu kí tự, chúng ta có kiểu dữ liệu char để biểu diễn, còn xâu kí tự thì có hai cách khác nhau:

Sử dụng một mảng gồm nhiều phần tử kiểu char.
Sử dụng thư viện con <string> đã được xây dựng sẵn trong C++. Cách này được ưa chuộng hơn vì thao tác dữ liệu tốt hơn.

II. Thư viện `<string>` trong C++

Thư viện chuẩn của C++ cung cấp cho chúng ta một thư viện con <string> hỗ trợ việc lưu trữ các xâu kí tự (xâu kí tự) và rất nhiều các phương thức xử lý đi kèm.

1. Khai báo và truy cập các phần tử xâu

Để khai báo một xâu sử dụng thư viện <string>, đầu tiên ta cần khai báo thư viện và không gian tên chứa nó bằng cú pháp:

#include <string>

using namespace std;

Sau đó, khai báo một xâu bằng cú pháp:

string {Tên_xâu};

Vẫn như thường lệ, {Tên_xâu} là một định danh do người dùng đặt ra, miễn là không trùng với từ khóa của hệ thống. Ta không cần khai báo độ dài của xâu, mà mỗi khi thêm một kí tự vào thì string sẽ tự động điều chỉnh độ dài của xâu cho vừa khớp với số lượng kí tự. Khi khai báo xâu, mặc định xâu đó sẽ là xâu rỗng (không có kí tự nào).

Các kí tự trong xâu sẽ được đánh số từ $0$ . Để truy cập một vị trí trong xâu (với điều kiện vị trí đó hiện đang có kí tự hoặc đã được khởi tạo), ta dùng cú pháp:

{Tên_xâu}[{Vị_trí}]

Khá giống với mảng đúng không nào! Sau khi truy cập, mỗi vị trí trong xâu có thể được thao tác giống như một kí tự và kết hợp với các câu lệnh cũng như toán tử. Ví dụ, gán một biến $c$ bằng kí tự ở vị trí số $2$ của xâu $s$ bằng cú pháp:

char c = s[2];

2. Cách nhập xuất một xâu

2.1. Nhập xuất các biến kiểu `<string>`

Khi nhập xuất một biến xâu kí tự, ta có thể coi xâu đó như một biến đơn và sử dụng hai câu lệnh cin và cout để nhập xuất. Cú pháp như sau:

cin >> {Tên_biến_xâu}; // Nhập vào một biến xâu.
cout << {Tên_biến_xâu}; // Viết ra một biến xâu.

Tuy nhiên, có một lưu ý khi sử dụng lệnh cin đối với string, đó là nếu như trong quá trình nhập liệu gặp phải dấu cách, thì việc nhập sẽ bị ngắt tại đó, cho dù người dùng có nhập thêm bao nhiêu kí tự đi chăng nữa thì xâu cũng sẽ chỉ lưu trữ phần ở phía trước dấu cách mà thôi. Cùng xem ví dụ dưới đây:

#include <iostream>
#include <string>

using namespace std;

int main()
{
    string name;
    cin >> name;
        
    cout << "Tên vừa nhập là: " << name;

    return 0;
}

Nếu người dùng nhập vào một tên là Vũ Quế Lâm, thì khi chạy chương trình ta sẽ thu được kết quả này:

Tên vừa nhập là: Vũ

Do đó, trong trường hợp cần đọc vào một xâu có cả dấu cách, ta sẽ sử dụng kết họp hai cú pháp:

getline(cin, {Tên_xâu});

Lệnh getline() sẽ thu nhận cả dòng dữ liệu nhập vào, bao gồm cả những dấu cách. Nó sẽ dừng việc đọc lại khi gặp kí tự \n - tức là kí tự xuống dòng:

#include <iostream>
#include <string>

using namespace std;
    
int main()
{
    string name;
    getline(cin, name);
        
    cout << "Tên vừa nhập là: " << name;

    return 0;
}

Lúc này, với tên nhập vào là Vũ Quế Lâm, chạy chương trình sẽ thu được kết quả chính xác:

Tên vừa nhập là: Vũ Quế Lâm

2.2. Nhập nhiều xâu kí tự hoặc chuyển đổi từ nhập số sang nhập xâu bằng `getline()`

Nếu như chúng ta chỉ nhập một xâu kí tự duy nhất, thì sẽ không có điều gì đáng lưu tâm cả, bạn chỉ cần lựa chọn giữa cin và getline(cin) tùy vào việc xâu bạn nhập vào có dấu cách hay không. Tuy nhiên, khi dữ liệu đầu vào có nhiều xâu kí tự khác nhau, hoặc khi dữ liệu đầu vào bao gồm cả số và xâu, thì câu chuyện sẽ khác đi. Về bản chất, khi các bạn nhập bất cứ thứ gì vào từ bàn phím, chúng sẽ được đẩy vào bộ nhớ đệm, rồi hàm cin sẽ "đọc" dữ liệu ra từ bộ nhớ đệm rồi nạp vào biến.

Chẳng hạn, nếu như các bạn nhập vào một số là $123,$ rồi ấn phím Enter (chính là kí tự xuống dòng), thì $123$ và kí tự \n sẽ được đẩy vào bộ nhớ đệm trước, sau đó hàm cin mới "quét qua" dữ liệu trong bộ nhớ đệm và đưa nó vào biến phía sau. Trong trường hợp biến phía sau là một biến kiểu số, thì chỉ có các chữ số mới được ghi nhận vào biến, còn những kí tự như và \n sẽ bị bỏ qua, nhờ đó nên trong trường hợp đọc nhiều số khác nhau, chương trình vẫn sẽ phân tách đúng các số, dù các bạn dùng dấu cách hay dấu xuống dòng. Tuy nhiên, nếu như theo sau số nhập vào là một kí tự, hoặc một xâu kí tự, thì nó sẽ đọc được cả kí tự \n (vì kí tự \n chỉ bị bỏ qua chứ nó vẫn còn tồn tại trong bộ nhớ đệm), dẫn đến xâu kí tự sẽ bị đọc sai. Cùng xem một ví dụ dưới đây:

int main()
{
    int id;
    cin >> id; // Nhập mã số sinh viên.

    string name;
    getline(cin, name);

    cout << id << endl << name;

    return 0;
}

Nếu như nhập vào dữ liệu là $id = 1$ và $name=$ Nguyen Van A, thì khi chạy chương trình các bạn sẽ thấy kết quả in ra chỉ có như sau:

Nguyên do là vì, khi nhập xong số $1,$ chúng ta sẽ nhấn Enter hoặc dấu cách. Biến $id$ chỉ có thể đọc được số $1,$ còn kí tự dấu cách hoặc xuống dòng vẫn nằm lại trong bộ nhớ đệm. Hàm getline(cin, name) tiếp theo sẽ đọc luôn cả những kí tự đó, dẫn đến hai trường hợp sau:

Nếu kí tự còn lại là dấu cách, thì kí tự đó sẽ bị thêm vào đầu của xâu kí tự $name$ .
Nếu kí tự còn lại là dấu xuống dòng, thì hàm getline() sẽ dừng lại luôn và xâu kí tự $name$ sẽ bị mất giá trị.

Tựu chung lại, dữ liệu của chúng ta sẽ bị sai! Vậy giải pháp là gì? Chúng ta cần xóa bộ nhớ đệm trước khi nhập một xâu (nên làm như vậy dù nhập một xâu hay nhiều xâu). Hàm cin trong C++ cung cấp phương thức cin.ignore() để làm điều đó. Cú pháp như sau:

cin.ignore(n, c);

Phương thức cin.ignore() sẽ xóa đi $n$ kí tự trong bộ nhớ đệm cho tới khi gặp kí tự $c$ thì dừng lại, và luồng nhập dữ liệu sẽ bắt đầu từ kí tự phía sau kí tự $c$ . Nếu như ta để trống tham số thì chương trính sẽ tự động hiểu là chỉ xóa $1$ kí tự trong bộ nhớ đệm. Điều này khá hữu ích khi nhập xâu ngay sau một số, vì chúng ta sẽ có thói quen dùng một dấu cách hoặc một dấu xuống dòng sau khi nhập số. Như vậy, đoạn code phía trên có thể sửa lại như sau:

int main()
{
    int id;
    cin >> id; // Nhập mã số sinh viên.

    string name;
    cin.ignore();
    getline(cin, name);

    cout << id << endl << name;

    return 0;
}

Lúc này, kết quả sẽ trở nên chính xác với bộ dữ liệu nhập vào:

1
Nguyen Van A

2.3. Xuất ra các hằng xâu hoặc hằng kí tự

Trong trường hợp cần viết các hằng xâu hoặc hằng kí tự trong C++, ta có quy tắc như sau:

Nếu viết ra một kí tự, thì đặt kí tự đó trong cặp ngoặc '' hoặc "". Ví dụ, viết ra kí tự a thì có thể viết cout << 'a'; hoặc cout << "a"; đều được.
Nếu viết ra một chỗi có nhiều hơn $1$ kí tự, thì cần đặt xâu trong cặp dấu "". Ví dụ, khi muốn viết ra thông báo Bạn đã đăng nhập thành công thì phải viết là cout << "Bạn đã đăng nhập thành công";.

III. Một số thao tác cơ bản trên xâu kí tự

1. Duyệt xâu

Để duyệt qua các phần tử trên xâu, ta sử dụng một vòng lặp từ vị trí đầu tiên tới vị trí cuối cùng của xâu. Thư viện <string> cung cấp cú pháp {Tên_xâu}.size() để lấy độ dài của xâu, mà ta biết rằng các phần tử trong xâu được đánh số từ vị trí $0,$ nên cú pháp duyệt xâu như sau:

for ({Biến_đếm} = {Vị_trí_đầu}; {Biến_đếm} < {Tên_xâu}.size(); {Tăng_giảm_biến_đếm})
{
    {Các_câu_lệnh};
}

Chẳng hạn, để duyệt các phần tử của một xâu $s$ từ đầu tới cuối xâu, ta viết như sau:

for (int i = 0; i < s.size(); ++i)

Nếu muốn duyệt một đoạn nhỏ trên xâu, hoặc duyệt ngược từ cuối về đầu xâu chẳng hạn, chỉ cần biến đổi vòng lặp một chút xíu. Bạn đọc hãy thử tự suy nghĩ về vấn đề này nhé.

Ngoài ra, chúng ta còn có thể duyệt qua tất cả các phần tử trong xâu theo cú pháp duyệt trực tiếp phần tử như sau:

for (char {Tên_biến_kí_tự}: {Tên_xâu})
{
    {Các_câu_lệnh};
}

Ví dụ, muốn duyệt qua mọi phần tử của xâu $s$ bất kỳ theo cách này, ta viết:

for (char c: s)

Tuy nhiên, cách duyệt này chỉ có thể duyệt được mọi phần tử của xâu theo thứ tự từ trái qua phải, và buộc phải duyệt qua tất cả xâu. Vì thế nó không được ưu tiên như cách thứ nhất.

2. Tìm kiếm tuần tự trên xâu

Bài toán đặt ra rất đơn giản: Cho xâu kí tự $s$ chỉ gồm toàn chữ cái latin in thường và một kí tự chữ cái $c$ bất kỳ, hãy đếm số lượng kí tự $c$ trong xâu $s?$

Bằng cách duyệt qua các phần tử trên xâu và áp dụng các toán tử, ta có thể giải quyết bài toán này như sau:

#include <iostream>
#include <string>

using namespace std;

int main()
{
    string s;
    char c;
    cin >> s;
    cin >> c;

    int cnt = 0; // Biến đếm số kí tự khác c trong xâu.
    for (int i = 0; i < s.size(); ++i)
	if (s[i] == c) // Nếu kí tự ở vị trí i khác c thì tăng biến đếm lên.
	    ++cnt;

    cout << cnt;

    return 0;
}

Bài toán tìm kiếm trên xâu có thể biến đổi linh hoạt theo nhiều cách khác nhau, chỉ cần các bạn hiểu rõ về cách đánh số thứ tự của kí tự và cách duyệt qua các kí tự trong xâu là sẽ làm được. Hãy sang phần bài tập áp dụng để vận dụng bài tập thêm nhé!

IV. Các thao tác xử lý xâu kí tự

1. Phép so sánh

Như đã đề cập ở phần I, máy tính sử dụng một bảng chữ cái gồm $256$ kí tự được đánh số từ $0$ tới $255,$ mỗi kí tự đều được mã hóa bằng những bit nhị phân, gọi là bảng mã ASCII. Hai xâu kí tự được so sánh với nhau dựa trên bảng mã này. Quy trình so sánh hai xâu kí tự $X$ và $Y$ trong C++ diễn ra như sau:

Các kí tự được đánh số từ $0$ ở mỗi xâu, sau đó tìm vị trí $i$ đầu tiên sao cho $X_i \ne Y_i$ . Khi đó, nếu $X_i$ nằm sau $Y_i$ trong bảng mã ASCII thì xâu $X$ sẽ lớn hơn xâu $Y,$ ngược lại xâu $Y$ lớn hơn xâu $X$ .
Trong trường hợp không tìm được vị trí $i$ thỏa mãn thì xâu nào dài hơn sẽ là xâu lớn hơn.
Nếu cả hai trường hợp trên không xảy ra thì kết luận xâu $X$ bằng xâu $Y$ .

Các toán tử >, <, <=, >=, ==, != có thể được sử dụng trực tiếp để so sánh hai kí tự hoặc hai xâu trong C++, tất nhiên là theo quy tắc nêu trên vì hệ thống đã có sẵn các toán tử so sánh nạp chồng cho kiểu xâu.

Ví dụ 1: Chương trình dưới đây sẽ so sánh hai xâu kí tự và đưa ra xâu lớn hơn

#include <iostream>
#include <string>

using namespace std;

int main()
{
    string s1 = "Tôi đi học";
    string s2 = "Tôi đi ngủ";

    cout << "Chuỗi lớn hơn là: "
    if (s1 > s2)
        cout << s1;
    else
	cout << s2;

    return 0;
}

Kết quả chạy chương trình sẽ là:

Chuỗi lớn hơn là: Tôi đi ngủ

Chuỗi Tôi đi học nhỏ hơn xâu Tôi đi ngủ vì kí tự n lớn hơn kí tự h trong bảng mã ASCII. Một điều rất thú vị trong so sánh xâu, đó là mặc dù số $100$ lớn hơn số $90,$ nhưng xâu 100 sẽ nhỏ hơn xâu 90, vì kí tự 1 đứng trước kí tự 9 trong bảng mã ASCII. Do đó, khi so sánh các số ở dạng xâu cần hết sức chú ý (vấn đề này sẽ được nhắc tới trong chủ đề Xử lý số nguyên lớn ở phần lập trình thi đấu).

Ví dụ 2: In ra các kí tự chữ cái latin in thường trên một dòng (không có dấu cách):

#include <iostream>

using namespace std;

int main()
{
    for (char c = 'a'; c <= 'z'; ++c)
        cout << c;

    return 0;
}

Kết quả chạy chương trình:

abcdefghijklmnopqrstuvwxyz

2. Phép nối xâu

Khác với phép cộng ở kiểu số, toán tử + khi được kết hợp với hai xâu có ý nghĩa là nối hai xâu đó với nhau. Ví dụ dưới đây có thể làm rõ:

#include <iostream>
#include <string>

using namespace std;

int main()
{
    string s1 = "Ngày mai ";
    string s2 = "tôi đi học.";

    cout << s1 + s2;

    return 0;
}

Kết quả chạy chương trình sẽ là:

Ngày mai tôi đi học.

Lưu ý:

Đặc điểm của phép cộng xâu là xâu đứng sau toán tử + sẽ được nối vào phía sau của xâu đứng trước toán tử +. Ví dụ, nếu như ta viết cout << s2 + s1; ở chương trình trên, thì kết quả sẽ trả ra là tôi đi học.Ngày mai thay vì Ngày mai tôi đi học.
Phép nối xâu bản chất là tạo ra một bản sao của xâu ban đầu, nối bản sao đó với xâu cần nối rồi gán ngược trở lại xâu ban đầu. Vì vậy, phép nối bằng toán tử + sẽ có thời gian chạy khá lâu trong các trường hợp xâu dài, cần hết sức lưu ý khi sử dụng.

3. Lấy số hiệu trong bảng mã ASCII của một kí tự

Bằng kĩ thuật ép kiểu, ta có thể xác định được số thứ tự trong bảng mã ASCII của một kí tự $c$ bất kỳ, với $c$ là một biến kí tự hoặc hằng kí tự. Cú pháp như sau:

(int) (c);

Nếu $c$ là một hằng kí tự thì ta cần đặt nó trong cặp dấu '', còn nếu là biến kí tự thì không cần. Ví dụ, muốn biết số thứ tự của kí tự a, ta có câu lệnh(int)('a') sẽ trả ra kết quả $97,$ còn nếu muốn biết số thứ tự của một biến kí tự $c,$ thì chỉ cần viết (int)(c) thôi. Số hiệu của kí tự phải được sử dụng trong các câu lệnh chứ không được đặt nó đứng đơn lẻ.

Hoàn toàn tương tự, ta có thể xác định được kí tự ứng với số hiệu $x$ trong bảng mã ASCII bằng cú pháp ép kiểu char ngược lại:

(char) (x);

Chẳng hạn, câu lệnh cout << (char) (48); sẽ trả ra kết quả là kí tự chữ số 0.

Có rất nhiều bài tập ứng dụng phần lấy số hiệu kí tự này, chẳng hạn như đổi từ kí tự số sang số đếm được, hay đổi chữ in hoa thành in thường và ngược lại,...thông qua việc đánh giá chênh lệch giữa số hiệu ASCII của các kí tự.

4. Các hàm xử lý xâu có sẵn trong thư viện của C++

Giả sử ta khai báo một xâu kí tự $s$ bằng cú pháp: string s;. Bảng dưới đây liệt kê những phương thức xử lý dữ liệu thường dùng nhất, được hỗ trợ sẵn trong thư viện con <string> dành cho xâu $s$ :

Thư viện <string> cũng cung cấp các hàm liên quan tới chuyển đổi giữa xâu - số ở bảng dưới đây:

Ngoài ra còn rất nhiều phương thức khác được xây dựng sẵn để hỗ trợ người dùng, bạn đọc có thể tra cứu ở địa chỉ: <i>Lớp string trong C++</i>.

5. Xóa các kí tự trong xâu

Như bạn đọc đã thấy ở mục $5,$ khi cần xóa một kí tự hoặc một xâu con trong xâu ban đầu, ta có thể sử dụng hàm erase() của thư viện <string>. Tuy nhiên, khi xóa các kí tự trong xâu, thì sẽ xảy ra tình huống là các kí tự phía sau đoạn được xóa sẽ đẩy lên phía trên và nối liền với đoạn phía trước, dẫn đến số thứ tự của các kí tự trong xâu được đánh số lại. Nếu không cẩn thận khi xử lý sẽ rất dễ đưa ra kết quả sai. Cùng xem một ví dụ dưới đây, ta sẽ xóa các dấu cách trong một xâu và đưa ra xâu đó sau khi xóa:

#include <bits/stdc++.h>

using namespace std;

int main()
{
    string s;
    getline(cin, s);

    for (int i = 0; i < s.size(); ++i)
	if (s[i] == ' ')
            s.erase(i, 1);

    cout << s;

    return 0;
}

Nếu chạy đoạn chương trình trên với $s$ bằng ab c css e ad, kết quả trả về sẽ như sau:

abc cssead

Ta thấy kết quả hoàn toàn sai, điều này là do các kí tự bị đánh số lại, chiều dài xâu cũng thay đổi mỗi khi xóa dẫn đến vị trí của các dấu cách cũng thay đổi theo. Để khắc phục điểm này, khi xóa các kí tự hoặc xâu con trong một xâu, hãy xóa từ phải qua trái, và luôn đảm bảo rằng phần xâu phía sau đoạn bị xóa đi ở mỗi lần xóa sẽ không còn cần sử dụng đến nữa!

#include <bits/stdc++.h>

using namespace std;

int main()
{
    string s;
    getline(cin, s);

    for (int i = s.size() - 1; i >= 0; --i)
	if (s[i] == ' ')
            s.erase(i, 1);

    cout << s;
    
    return 0;
}

Với đoạn code mới này, kết quả sẽ trả ra hoàn toàn chính xác:

abccssead

V. Chuỗi kí tự theo phong cách ngôn ngữ C (đọc thêm)

Vì C++ có nền tảng là ngôn ngữ C, nên cũng hỗ trợ xử lý xâu kí tự theo phong cách ngôn ngữ C. Trong C, xâu kí tự được biểu diễn dưới dạng một mảng chứa các kí tự. Cú pháp để khai báo xâu phong cách C là:

char {Tên_xâu}[{Kích_thước_xâu}];

Các kí tự trong xâu kiểu C vẫn được đánh số từ $0$ . Vì nó là mảng nên cách sử dụng cũng giống như mảng thông thường. Ví dụ khai báo một xâu Hello theo phong cách C, ta có thể viết theo quy tắc khởi tạo mảng như sau:

char test_str[6] = {'H', 'e', 'l', 'l', 'o', '\0'};

hoặc viết theo quy tắc khởi tạo xâu, thì kích thước xâu sẽ tự động điều chỉnh cho khớp với số lượng kí tự:

char test_str[] = "Hello";

Các hàm xử lý với xâu theo phong cách C được hỗ trợ không nhiều, được liệt kê ở bảng dưới đây. Nói chung ta nên ưu tiên sử dụng thư viện <string> vì nó hỗ trợ xử lý xâu cực kỳ tốt, đặc biệt trong các bài toán lập trình thi đấu cần yêu cầu tốc độ lập trình nhanh.

VI. Một số bài toán đơn giản về xâu kí tự

1. Xâu đối xứng

Đề bài

Một xâu kí tự được gọi là đối xứng nếu như khi viết ngược nó lại, ta vẫn thu được một xâu mới giống xâu ban đầu. Chẳng hạn, aba, aaccaa,...là các xâu đối xứng, còn các xâu a, ba, vuquelam,...thì không phải.

Yêu cầu: Cho trước một xâu kí tự $s,$ hãy xác định xâu đó có phải đối xứng hay không?

Input:

Một dòng duy nhất chứa xâu kí tự $s$ chỉ bao gồm các chữ cái latin in thường.

Ràng buộc:

Độ dài xâu $s$ không vượt quá $10^6$ .

Output:

In ra YES nếu như xâu $s$ là xâu đối xứng, ngược lại in ra NO.

Sample Input:

aabbaa

Sample Output:

YES

Ý tưởng

Cách làm dễ nhất là sử dụng một xâu $s_1,$ lưu các kí tự của xâu $s$ theo chiều ngược lại, rồi so sánh hai xâu. Cách làm này không phải một cách hay, vì phép cộng xâu trong C++ sẽ có độ phức tạp bằng độ dài của xâu mới, ngoài ra phép so sánh hai xâu cuối cùng cũng sẽ có độ phức tạp bằng đúng độ dài xâu. Vì thế, cách này chưa tối ưu.

Gọi $n$ là độ dài của xâu kí tự và coi rằng đánh số các kí tự trong xâu từ vị trí $0$ tới vị trí $n - 1$ . Ta nhận xét thấy, nếu một xâu là đối xứng, thì cặp kí tự thứ $i$ và $n - i - 1$ sẽ giống nhau. Vì thế, chỉ cần sử dụng một vòng lặp duyệt $i$ từ $0$ tới $\left(\left\lfloor{\frac{n}{2}} \right\rfloor - 1\right)$ rồi kiểm tra cặp kí tự $i$ và $n - i - 1$ có giống nhau hay không, nếu tồn tại một cặp khác nhau thì kết luận luôn xâu không phải đối xứng.

Bằng cách này, chúng ta giảm được số lần lặp xuống chỉ còn tối đa $\left\lfloor{\frac{n}{2}} \right\rfloor$ lần.

Cài đặt

#include <bits/stdc++.h>
	
using namespace std;
	
bool is_palindrome(const string& s)
{
    int n = s.size();
    for (int i = 0; i < n; ++i)
        if (s[i] != s[n - i - 1])
            return false;
						  
    return true;
}
	
main()
{
    string s;
    cin >> s;
	
    if (is_palindrome(s))
        cout << "YES";
    else 
        cout << "NO";

    return 0;
}

2. Chuẩn hóa xâu

Đề bài

Cho một xâu kí tự $s$ chỉ gồm các chữ cái latin in thường và in hoa cùng các dấu cách. Một xâu được gọi là chuẩn hóa nếu như nó thỏa mãn các điều kiện sau:

Không bao gồm các dấu cách thừa ở đầu và cuối xâu.
Gồm nhiều từ, mỗi từ bắt đầu bằng một chữ cái in hoa và theo sau là các chữ cái in thường.
Giữa các từ phân tách nhau bằng đúng một dấu cách.

Yêu cầu: Hãy chuẩn hóa xâu $s$ và đưa ra kết quả?

Input:

Một dòng duy nhất chứa xâu kí tự $s$ chỉ bao gồm các chữ cái latin và dấu cách.

Ràng buộc:

Độ dài xâu $s$ không vượt quá $1000$ .

Output:

In ra xâu $s$ sau khi đã chuẩn hóa.

Sample Input:

     Toi ten lA nhaT MINH

Sample Output:

Toi Ten La Nhat Minh

Ý tưởng

Cách làm hoàn toàn đơn giản như sau:

Đầu tiên xóa các dấu cách thừa ở đầu và cuối xâu, sử dụng hàm erase() của thư viện <string>.
Sau đó duyệt qua các kí tự của xâu $s,$ $s,$ lần lượt xử lý các trường hợp kí tự đó là chữ thường, chữ hoa hay dấu cách.
- Nếu là chữ thường mà đứng ở đầu một từ thì phải viết hoa nó lên, còn là chữ hoa mà không đứng đầu một từ thì viết thường nó.
- Nếu là dấu cách thì ta bỏ qua không quan tâm tới nó.
- Nếu kí tự đó là kí tự đầu tiên của mỗi từ thì in thêm ra một dấu cách.
- Cuối cùng in ra kí tự vừa xử lý.

Tuy nhiên, cần lưu ý trong bài này, xâu nhập vào có dấu cách, vì thế ta cần sử dụng getline() để nhập xâu.

Cài đặt

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

void enter(string& s)
{
    getline(cin, s);	
}
	
void solution(string& s)
{
    // Xóa các dấu cách thừa ở đầu xâu và cuối xâu.
    while (s[0] == ' ')
        s.erase(0, 1);
    while (s.back() == ' ')
        s.erase(s.size() - 1, 1);

    for (int i = 0; i < (int)s.size(); ++i)
    {
        if (s[i] == ' ')
            continue;
        else if (s[i] == '.') // Kí tự dấu chấm kết thúc xâu.
            cout << s[i];
        else if (s[i - 1] == ' ' || i == 0) // Kí tự đầu tiên của mỗi từ.
        {
            if ('a' <= s[i]& & s[i] <= 'z')
                s[i] = (char)(s[i] - 32);

            // Nếu không phải kí tự đầu tiên của xâu thì in ra
            // một dấu cách để phân tách với từ phía trước.
            if (i != 0) 
                cout << ' ';
            cout << s[i];
        }
        // Nếu không phải kí tự đầu tiên của từ mà bị viết hoa thì viết thường nó lại.
        else if (s[i - 1] != ' ') 
        {
            if ('A' <= s[i]& & s[i] <= 'Z')
                s[i] = (char)(s[i] + 32);
            cout << s[i];
        }
    }
}
	
int main()
{
    string s;
	
    enter(s);
    solution(s);
	
    return 0;
}

VII. Tài liệu tham khảo

I. Dữ liệu dạng văn bản

1. Bảng kí tự ASCII

2. Kí tự và xâu kí tự

II. Thư viện <string> trong C++

1. Khai báo và truy cập các phần tử xâu

2. Cách nhập xuất một xâu

2.1. Nhập xuất các biến kiểu <string>

2.2. Nhập nhiều xâu kí tự hoặc chuyển đổi từ nhập số sang nhập xâu bằng getline()

2.3. Xuất ra các hằng xâu hoặc hằng kí tự

III. Một số thao tác cơ bản trên xâu kí tự

1. Duyệt xâu

2. Tìm kiếm tuần tự trên xâu

IV. Các thao tác xử lý xâu kí tự

1. Phép so sánh

2. Phép nối xâu

3. Lấy số hiệu trong bảng mã ASCII của một kí tự

4. Các hàm xử lý xâu có sẵn trong thư viện của C++

5. Xóa các kí tự trong xâu

V. Chuỗi kí tự theo phong cách ngôn ngữ C (đọc thêm)

VI. Một số bài toán đơn giản về xâu kí tự

1. Xâu đối xứng

Đề bài

Ý tưởng

Cài đặt

2. Chuẩn hóa xâu

Đề bài

Ý tưởng

Cài đặt

VII. Tài liệu tham khảo

Mục lục

II. Thư viện `<string>` trong C++

2.1. Nhập xuất các biến kiểu `<string>`

2.2. Nhập nhiều xâu kí tự hoặc chuyển đổi từ nhập số sang nhập xâu bằng `getline()`