- title Xâu ký tự (String) - Xâu ký tự (String) === - ###### ✍️ Author: 2School Guideline ###### 📋 Content: [TOC] - Trước khi đi vào bài viết, tụi mình xin nói thêm một số số điều nho nhỏ về **xâu ký tự** trong **C++** (string) và trong **C** (char*). Nếu các bạn có đọc một số code mẫu các bài tập về xâu ký tự, thì mọi người sẽ thấy sẽ có một số code sử dụng kiểu `char*` thay vì `string` như tụi mình đề cập đến. VD như `char s[50]` hay `char* s[50]`, đây là các kiểu dùng xâu ký tự trong **C**, và qua tham khảo ý kiến và nhận thấy ưu điểm của `string` nên tụi mình quyết định chỉ đề cập đến cấu trúc `string` trong bài viết thôi nhé. # 1. Giới thiệu các khái niệm ## Ký tự trong C++ Ký tự trong C++ có bộ nhớ là 1 byte (8 bit). Một ký tự có thể đại diện cho một số nguyên dương trong khoảng từ $[-127, 127]$, ký tự có thể được coi như một kiểu dữ liệu `int` nhưng chỉ có 8 bit. Mọi người có thể xem đoạn code sau ```cpp=

include using namespace std; int main(){ char c = 'A'; int n = c; cout << n; return 0; } ``` **Output** ``` 65 ``` Như chúng ta đã thấy, số $65$ được output chính là **số hiệu** của ký tự trong bảng mã **ASCII**. Mỗi ký tự đều mang một **số hiệu** độc lập và cố định. Đoạn code dưới đây sẽ biểu diễn một vài **số hiệu** của một vài ký tự ```cpp=

include using namespace std; int main(){ for(int i = 32; i <= 127; i){ cout << i << " : " << char(i) <<'\n'; } return 0; } ``` **Output** ``` ... 54 : 6 55 : 7 56 : 8 57 : 9 58 : : 59 : ; 60 : < ... ``` Thao tác `char(i)` trong đoạn dùng để **gọi** ký tự có **số hiệu** là $i$ Lưu ý : Do các ký tự có **số hiệu** < 32 thường không sử dụng trong các bài toán thông thường ngoài ra có thể gây lỗi và compile error nên tụi mình sẽ không nhắc đến chúng ## String trong C Như một số bài viết trước có giới thiệu, xâu ký tự trong C++ được khai báo bằng cấu trúc `string = "xâu ký tự cần dùng"`. `string` cũng có thể được "coi" như một mảng ký tự. VD : ```cpp= string s = "abdcdbc"; string t = ""; //lưu ý xâu có thể khai báo rỗng bằng "" ``` Xét xâu $s$ ở ví dụ trên :  Các ký tự trong xâu $s$ của ta sẽ được đánh số từ $0$ đến $n-1$, với $n$ là độ dài của xâu $s$. Trong xâu $s$ trên, ta thấy $s_2$=$d$, $s_5$=$b$ Để sử dụng ký tự trong `string`, ví dụ ta muốn lấy ký tự thứ $5$ và thứ $2$ trong xâu $s$ ```cpp= string s = "abdcdbc"; cout << s[5] << '\n'; //trả về d cout << s[2] << '\n'; //trả về b ``` # 2. Một số thao tác hữu ích trên xâu ký tự ## Input, Output - Output cả xâu : ```cpp= string s; cin >> s; //2SGxinhdep cout << s << '\n'; //2SGxinhdep cout << s[3] <<'\n'; //x ``` - Input xâu **không bao gồm** dấu cách : VD ta muốn nhập vào xâu : "2SGBanTin" ```cpp= string s; cin >> s; //2SGBanTin cout << s; //2SGBanTin ``` - Input xâu **bao gồm** dấu cách : VD ta muốn nhập vào xâu : "2SG Ban Tin" ```cpp= string s; getline(cin, s); //2SG Ban Tin cout << s; //2SG Ban Tin ``` Hàm `getline(cin, s)` có ý nghĩa là nhập vào tất cả ký tự trên một dòng (bao gồm cả dấu cách). Nếu trong trường hợp ta sử dụng `cin >> s` để nhập ```cpp= string s; cin >> s; //2SG Ban Tin cout << s; //2SG ``` Hàm `cin` chỉ lấy cả xâu trước dấu cách hoặc xuống dòng ## Các thao tác trên string ### Iterator trên string Trong `string`, chúng ta sử dụng `begin` và `end` để biểu diễn trong một số thao tác của xâu. VD ta đang có xâu $s$ và ta muốn sắp xếp lại các ký tự theo thứ tự từ điển (từ a đến z) : ```cpp= string s = "abdcdbc"; sort(s.begin(), s.end()); //s.begin() là dùng để lấy vị trí bắt đầu thao tác //s.end() là vị trí trước vị trí cuối cùng //[first, last) cout << s; //abbccdd ``` Cấu trúc `string` giống `vector` trong con trỏ đầu và cuối mảng, các bạn có thể xem ảnh để dễ hình dung :  Giả sử ta muốn sắp xếp từ vị trí $1$ đến vị trí trước vị trí cuối cùng : ```cpp= string s = "abdcdbc"; sort(s.begin()+1, s.end()-1); cout << s; //abbcddc ``` Các bạn có thể xem ảnh về cách `begin` và `end` hoạt động trong `string` và cả `vector`  ### Thao tác gán chuỗi Thao tác gán chuỗi là một thao tác vừa hữu dụng nhưng cũng vừa "nguy hiểm" đối với những người chưa xài thành thạo. Xét hai đoạn code sau : Code 1: ```cpp= string s = ""; for(int i = 1; i <= 100000; i) s = s + "a"; ``` ``` chạy trong 0.375s ``` Code 2: ```cpp= string s = ""; for(int i = 1; i <= 100000; ++i) s += "a"; ``` ``` chạy trong 0.035s ``` Vì sao lại có sự khác biệt lớn như vậy ? Vấn đề nằm ở thao tác `+`. Nếu ta lấy hai xâu $s$ và $t$ : - `s = s + t` sẽ tốn chi phí là tổng độ dài của $s$ và $t$ - `s += t` sẽ tốn chi phí là độ dài của $t$ Đây chính là điểm khác biệt, có rất nhiều người sẽ bị mắc phải lỗi này khiến chương trình chạy chậm, để giải thích thì thao tác thứ nhất, compiler sẽ copy xâu $s$ rồi mới cộng thêm xâu $t$. Còn ở thao tác thứ 2, compiler chỉ copy lại xâu $t$ và thêm vào **cuối xâu** $s$. Code 1 chạy chậm vì nó sẽ tốn chi phí là $O(\frac{100000 \times (100000+1)}{2})$, còn với Code 2 chỉ sẽ tốn $O(100000)$. ### So sánh chuỗi: Bạn có thể sử dụng các phép toán logic trên string nhưng cần chú ý rằng string sẽ so sánh các chuỗi dựa trên thứ tự từ điển chứ sẽ không so sánh theo độ dài của chuỗi như nhầm lẫn của nhiều bạn. Ví dụ: ```cpp= string s1 = "ab90"; string s2 = "ab123456"; if (s1 > s2) cout << s1; else cout << s2; ``` Output: ``` ab90 ``` * Bởi vì string so sánh theo thứ tự từ điển nên ở kí tự thứ 3 của 2 string, string s1 có kí tự lớn hơn string s1 ('9' > '1') nên string s1 lớn hơn string s2. ## Các thao tác khác Bên cạnh những thao tác thường sử dụng thì còn nhiều những thao tác khác nhưng do dung lượng của bài viết nên tụi mình sẽ không đề cập đến. Nếu các bạn muốn tham khảo có thể xem tại đây : [geeksforgeeks](https://www.geeksforgeeks.org/strings-in-cpp/) (Nguồn ảnh từ geeksforgeeks) **Các thao tác**   **Các iterator**  # 3. Xử lí số lớn: Như chúng ta đã biết ở những bài học trước, trong C có rất nhiều kiểu dữ liệu để lưu giá trị số nguyên như: `int`, `long long`,... nhưng kiểu dữ liệu có thể lưu được số có giá trị cao nhất là `long long` thì giới hạn cũng chỉ khoảng $2^{64}$. Vì thế, để lưu và tính toán với các giá trị lớn hơn thì ta phải xử lí số trên string để có được kết quả mong muốn. ## Phép cộng: ### Ý tưởng: * Chúng ta sẽ cộng kí tự chữ số của 2 chuỗi từ phải sang trái và mang theo nhớ sang các kí tự tiếp theo bên trái của chuỗi như quy tắc đặt tính rồi tính, ta đã từng học ở cấp 1. Ví dụ: $754 + 67$  Thực hiện phép tính từ phải qua trái ta có: * 4 cộng 7 bằng 11, viết 1 nhớ 1 * 5 cộng 6 bắng 11, thêm 1 bắng 12, viết 2 nhớ 1 * 7 thêm 1 bằng 8, viết 8 ### Cài đặt: * Nếu 2 chuỗi có độ dài khác nhau, ta phải thêm số $0$ vào đầu chuỗi ngắn hơn để các kí tự có thể tiếp tục tính toán. * Khi cộng thay vì cộng vào đầu chuỗi thì ta sẽ cộng vào cuối chuỗi rồi đảo ngược chuỗi lại, như thế thuật toán sẽ nhanh hơn vì tránh được trường hợp đã được nói đến trong [**Thao tác gán chuỗi**](https://hackmd.io/S1rtCmlXQ_-G2jK3-XFtlg?both

Thao-t%C3%A1c-g%C3%A1n-chu%E1%BB%97i) ở trên. :::spoiler **Code mẫu:** ```cpp= string pluss(string s1,string s2){ int equal = abs( (int) s1.size() - (int) s2.size()); // Tìm độ chênh lệch giữa độ dài 2 xâu if ( (int) s1.size() < (int) s2.size() ){ // Nếu xâu s2 lớn hơn xâu s1 thêm kí tự 0 vào s1 while (equal--){ s1 = "0" + s1; } } else if ( (int) s2.size() < (int) s1.size() ){ // Nếu xâu s1 lớn hơn xâu s2 thêm kí tự 0 vào s2 while (equal--){ s2 = "0" + s2; } } string ans = ""; int nho = 0; for (int i = (int) s1.size() - 1; i >= 0; --i){ int cur = (s1[i] - '0') + (s2[i] - '0'); cur += nho; int add = cur % 10; // Lấy số cộng vào chuỗi ans += char(add + '0') ; nho = cur / 10; // Cập nhật nhớ } if (nho != 0) // Nếu sau khi cộng xong biến nhớ vẫn còn giá trị thì ta phải thêm 1 vào đầu chuỗi ans+= "1"; reverse(ans.begin(),ans.end()); // Đảo ngược chuỗi về đúng chiều return ans; } ``` ::: ## Phép trừ: ### Ý tưởng: * Ta sẽ trừ từng kí tự từ phải sang trái, nếu chuỗi bị trừ có kí tự lớn hơn chuỗi trừ thì ta sẽ nhớ 1 vào phép trừ 2 kí tự bên trái kế tiếp. * Ví dụ:  ### Cài đặt: * Nếu 2 chuỗi có độ dài khác nhau, ta phải thêm số $0$ vào đầu chuỗi ngắn hơn để các kí tự có thể tiếp tục tính toán. * Nếu chuỗi bị trừ lớn hơn chuỗi trừ ta sẽ hoán đổi chuỗi bị trừ thành chuỗi trừ và chuỗi trừ thành chuỗi bị trừ rồi thêm dấu âm vào đầu kết quả. * Khi cộng thay vì cộng vào đầu chuỗi thì ta sẽ cộng vào cuối chuỗi rồi đảo ngược chuỗi lại, như thế thuật toán sẽ nhanh hơn vì tránh được trường hợp đã được nói đến trong [**Thao tác gán chuỗi**](https://hackmd.io/S1rtCmlXQ_-G2jK3-XFtlg?both

Thao-t%C3%A1c-g%C3%A1n-chu%E1%BB%97i) ở trên. * Vì sau khi trừ chuỗi có thể có những xóa 0 vô nghĩa ở đầu nên ta cần phải xóa hết những số 0 đó. :::spoiler **Code mẫu:** ```cpp= string subtract(string s1,string s2){ int equal = abs( (int) s1.size() - (int) s2.size()); // Tìm độ chênh lệch giữa độ dài 2 xâu if ( (int) s1.size() < (int) s2.size() ){ // Nếu xâu s2 lớn hơn xâu s1 thêm kí tự 0 vào s1 while (equal--){ s1 = "0" + s1; } } else if ( (int) s2.size() < (int) s1.size() ){ // Nếu xâu s1 lớn hơn xâu s2 thêm kí tự 0 vào s2 while (equal--){ s2 = "0" + s2; } } bool kt = true; if (s1 < s2){ // Nếu xâu s2 lớn hơn xâu s1 thì đáp án sẽ là số âm nên ta cần đánh dấu lại string s = s1; s1 = s2; // Đổi chuỗi trừ thành chuỗi bị trừ s2 = s; // Đổi chuỗi bị trừ thành chuỗi trừ kt = false; } string ans = ""; int nho = 0; for (int i = (int)s1.size() - 1; i>=0; i){ int cur = (s1[i] - '0') - (s2[i] - '0') - nho; if (cur < 0){ // Nếu số trừ ra là số âm thì ta cần lấy 1 từ cột bên trái kế tiếp rồi đánh dấu nhớ lại nho = 1; cur = cur + 10; } else nho = 0; ans += char(cur + '0'); } reverse(ans.begin(),ans.end()); while ((int)ans.size() > 1 && ans[0] == '0') // Vì có thể khi trừ xong các số ở đầu xâu bằng 0 nên ta phải xóa đi ans.erase(ans.begin()); if (!kt) // Nếu s2 lớn hơn s1 ta thêm dấu âm vào kết quả ans = "-" + ans; return ans; } ``` ::: ## Phép nhân: ### Ý tưởng * Ta nhân từng phần tử của chuỗi 2 với toàn bộ phần tử của chuỗi 1 từ phải sang trái, sau đó lấy kết quả cộng với chuỗi đáp án (mỗi lần dịch phần tử của chuỗi 2, khi cộng vào chuỗi đáp án, ta cần thêm '0' vào cuối chuỗi). Ví dụ:  * 8 nhân 6 bằng 48, viết 8 nhớ 4 8 nhân 4 bằng 32, thêm 4 bằng 36, viết 6 nhớ 3 8 nhân 7 bằng 56, thêm 3 bằng 59, viết 59 * 1 nhân 746 bằng 746, viết 746, dịch sang trái 1 hàng so với 5968 * Hạ 8 xuống 6 cộng 6 bằng 12 viết 2 nhớ 1 4 cộng 9 bằng 13 thêm 1 bằng 14, viết 4 nhớ 1 5 cộng 7 bằng 12 thêm 1 bằng 13, viết 13 * Vậy 746 x 18 = 13428 ### Cài đặt: * Vì sau khi trừ chuỗi có thể có những xóa 0 vô nghĩa ở đầu nên ta cần phải xóa hết những số 0 đó. :::spoiler **Code mẫu:** ```cpp= string multiply(string s1,string s2){ string ans = ""; for (int i = (int)s1.size() -1; i >= 0; --i){ string res = ""; int nho = 0; for (int j = (int)s2.size() -1; j >= 0; --j){ int cur = (s1[i] - '0') * (s2[j] - '0'); cur += nho; int add = cur % 10; res += char(add + '0'); nho = cur / 10; } if (nho != 0) res += char(nho + '0'); reverse(res.begin(),res.end()); for (int j = 1; j <= ((int)s1.size() - i -1); ++j) // Thêm số 0 vào cuối như tính chất của phép cộng res += "0"; ans = pluss(ans,res); // cộng đáp án trước với số mới tính được } while ((int)ans.size() > 1 && ans[0] == '0') // Nếu nhân đáp án là 0 thì phải xóa đi số 0 vô nghĩa ở đầu ans.erase(ans.begin()); return ans; } ``` ::: ## Phép chia lấy phần nguyên ### Phép chia lấy phần nguyên một số lớn với một số nguyên **Ý tưởng:** Ta sử dụng cách chia giống như học sinh tiểu học đặt tính phép chia: Liên tục lấy từng chữ số của số bị chia gộp vào một biến $cur$, sau đó chia $cur$ cho số chia, ghi thương nguyên vào một mảng kết quả, sau đó gán $cur$ bằng số dư của phép chia vừa thực hiện. **Cài đặt:** * Vì sau khi trừ chuỗi có thể có những xóa 0 vô nghĩa ở đầu nên ta cần phải xóa hết những số 0 đó. :::spoiler **Code mẫu:** ```cpp= string dividesmall(string a,long long b){ string ans = ""; int cur = 0; for (int i = 0; i < (int)a.size(); ++i){ cur = cur * 10 + (a[i] - '0'); ans += char(cur / b + '0'); cur %= b; } while ((int)ans.size() > 1 && ans[0] == '0') ans.erase(ans.begin()); return ans; } ``` ::: ### Phép chia lấy phần nguyên hai số lớn **Ý tưởng:** Ta sẽ áp dụng tìm kiếm nhị phân để tìm ra số nhân với số bị chia có tích bé hơn gần nhất với số chia. **Cài đặt:** * Vì ta dùng tìm kiếm nhị phân nên khi so sánh hai chuỗi l và r, ta cần thêm số 0 vào đầu chuỗi có độ dài nhỏ hơn để kết quả so sánh cho kết quả đúng. :::spoiler **Code mẫu:** ```cpp= string equal0(string s1,string s2){ if ((int)s1.size() >= (int)s2.size()) return s1; int add = (int)s2.size() - (int)s1.size(); while (add){ s1 = "0" + s1; } return s1; } string divide(string a,string b){ string l="0"; string r=a; string ans=""; while (equal0(l,r) <= equal0(r,l)){ string mid = dividesmall(pluss(l,r),2ll); string cur = multiply(mid,b); if (equal0(cur,a) <= equal0(a,cur)){ ans = mid; l = pluss(mid,"1"); } else { r = subtract(mid,"1"); } } return ans; } ``` ::: ## Phép chia lấy phần dư (mod) **Ý tưởng:** Ta nhận thấy rằng ```a % b``` sẽ bằng với ```a - b * (a / b)``` vì phép chia chúng ta đã cài đặt là phép chia lấy phần nguyên. **Cài đặt:** * Ta thấy những phép tính đó ta đã cài đặt ở trên vì thế ta chỉ cần sài lại những phép tính đó để lấy được đáp án. :::spoiler **Code mẫu:** ```cpp= string mod(string a,string b){ string ans = subtract(a,multiply(b,divide(a,b))); return ans; } ``` ::: # 4. Bài tập áp dụng ## [Bài 1:](https://codeforces.com/problemset/problem/71/A) **Tóm tắt đề**: Cho $n$ từ, một từ được coi là quá dài nếu từ đó có trên $10$ kí tự, những từ đó sẽ được viết tắt. Chữ viết tắt này được thực hiện như thế này: chúng ta viết chữ cái đầu tiên và chữ cái cuối cùng của một từ và giữa chúng chúng ta viết số chữ cái giữa chữ cái đầu tiên và chữ cái cuối cùng. Số đó thuộc hệ thập phân và không chứa bất kỳ số $0$ đứng đầu nào. Ví dụ: "internationalization" sẽ thành "i18n". Các từ còn lại xuất ra bình thường. **INPUT:** * Dòng đầu tiên ghi số $n$ $(1 \leq n \leq 100)$ * $n$ dòng tiếp, dòng thứ $i$ ghi từ $i$ bao gồm các chữ cái Latin viết thường và có độ dài từ $1$ đến $100$ ký tự. **OUTPUT:** * In $n$ dòng. Dòng thứ $i$ phải chứa kết quả của việc thay thế từ thứ $i$ trong dữ liệu đầu vào. **VD:** **INPUT:** ``` 4 word localization internationalization pneumonoultramicroscopicsilicovolcanoconiosis ``` **OUTPUT:** ``` word l10n i18n p43s ``` :::spoiler **Lời giải:** * Ta chỉ cần làm theo đề bài, kiểm tra nếu độ dài của chuỗi $\leq 10$ thì ta sẽ xuất chuỗi ra, còn lại lần lượt xuất kí tự đầu, độ dài và kí tự cuối của chuỗi. :::spoiler **Code mẫu:** ```cpp=

include using namespace std; int t;string s; int main() { cin >> t; while (t--){ cin>>s; if ((int)s.size() > 10){ cout << s[0]; cout << (int)s.size()-2; cout << s[(int)s.size()-1] << "\n"; } else cout << s << "\n"; } return 0; } ``` ::: ## Bài 2: **Đề bài:** Cho hai số nguyên dương $n$ và $k$. Ta định nghĩa $n! = 1 * 2 * 3 * … * n$. Tìm k chữ số đầu tiên của $n!$, với $k$ luôn nhỏ hơn hoặc bằng số chữ số của $n!$. **INPUT:** * 1 dòng duy nhất ghi hai số $n$ và $k$ $(2 \leq n \leq 500,1 \leq k \leq 18)$ **OUTPUT:** * 1 dòng duy nhất ghi $k$ chữ số đầu tiên của $n!$ **VD:** | INPUT | OUTPUT | | | | | 10 3 | 362 | * Giải thích: $10! = 3628800$, ba chữ số đầu tiên là $362$ :::spoiler **Lời giải:** * Đây là một bài áp dụng cơ bản của xử lí số lớn, ta chỉ cần nhân số lớn các xâu từ 1 đến $n$ rồi xuất ra k chữ số đầu tiên của chuỗi đáp án. :::spoiler **Code mẫu:** ```cpp=

include using namespace std; int n,k; string pluss(string s1,string s2){ int equal= abs( (int) s1.size() - (int) s2.size()); // Tìm độ chênh lệch giữa độ dài 2 xâu if ( (int) s1.size() < (int) s2.size() ){ // Nếu xâu s2 lớn hơn xâu s1 thêm kí tự 0 vào s1 while (equal--){ s1 = "0" + s1; } } else if ( (int) s2.size() < (int) s1.size() ){ // Nếu xâu s1 lớn hơn xâu s2 thêm kí tự 0 vào s2 while (equal--){ s2 = "0" + s2; } } string ans = ""; int nho = 0; for (int i = (int) s1.size() - 1; i >= 0; --i){ int cur = (s1[i] - '0') + (s2[i] - '0'); cur += nho; int add = cur % 10; // Lấy số cộng vào chuỗi ans += char(add + '0') ; nho = cur / 10; // Cập nhật nhớ } if (nho != 0) // Nếu sau khi cộng xong biến nhớ vẫn còn giá trị thì ta phải thêm 1 vào đầu chuỗi ans+= "1"; reverse(ans.begin(),ans.end()); // Đảo ngược chuỗi về đúng chiều return ans; } string multiply(string s1,string s2){ string ans = ""; for (int i = (int)s1.size() -1; i >= 0; --i){ string res = ""; int nho = 0; for (int j = (int)s2.size() -1; j >= 0; --j){ int cur = (s1[i] - '0') * (s2[j] - '0'); cur += nho; int add = cur % 10; res += char(add + '0'); nho = cur / 10; } if (nho != 0) res += char(nho + '0'); reverse(res.begin(),res.end()); for (int j = 1; j <= ((int)s1.size() - i -1); j) // Thêm số 0 vào cuối như tính chất của phép cộng res += "0"; ans = pluss(ans,res); // cộng đáp án trước với số mới tính được } while ((int)ans.size() > 1 && ans[0] == '0') // Nếu nhân đáp án là 0 thì phải xóa đi số 0 vô nghĩa ở đầu ans.erase(ans.begin()); return ans; } string solve(int n){ string ans = "1"; for (int i = 2; i <= n; ++i){ // Chạy từ 1 đến n để nhân vào đáp án int u = i; string cur = ""; while (u){ // Đổi u thành string cur += char(u % 10 + '0'); u/=10; } reverse(cur.begin(),cur.end()); ans = multiply(ans , cur); } return ans; } int main() { cin>> n>> k; string s = solve(n); for (int i = 0; i < k; ++i) // Xuất k chữ số đầu cout< by geeksforgeeks](https://www.geeksforgeeks.org/strings-in-cpp/)