Bài tập về các thao tác xử lí xâu năm 2024

Bài viết này sẽ tổng hợp các dạng bài tập liên quan đến xử lý xâu trong kỳ thi Tin học trẻ. Bài viết sẽ gồm 2 phần. Các bạn có thể xem thêm phần 2 tại đây!

Khái niệm Xâu

Xâu (tiếng anh là String) là một kiểu dữ liệu. Xâu là một dãy các ký tự trong bảng mã ASCII. Hiểu đơn giản, xâu là một chuỗi ký tự bao gồm chữ hoa, chữ thường, số và một số ký tự đặc biệt

Lưu ý: chữ ở đây được hiểu là các chữ cái trong bảng chữ cái tiếng anh.

Ví dụ về xâu (string): abc123, xin_chao, ToiThichHocLapTrinh!

Xâu trong Scratch

Trong Scratch, có 2 câu lệnh liên quan đến xử lý xâu:

length of … : Câu lênh này sẽ trả về số lượng ký tự có trong xâu.

Ví dụ, khi click vào câu lệnh “length of apple” thì câu lệnh này sẽ trả về số 5 vì chữ apple có 5 ký tự

letter … of … : Câu lệnh này sẽ giúp lấy ra ký tự ở vị trí nào đó của xâu.

Ví dụ, khi click vào câu lệnh “letter 1 of apple” thì câu lệnh này sẽ trả về chữ “a” vì ký tự thứ nhất (chữ cái thứ nhất) trong chuỗi (từ) apple là chữ “a”

Bài 1: Xử lý xâu – Đếm ký tự trong xâu

Nhân vật sẽ yêu cầu người chơi nhập vào một sâu bất kỳ. Sau đó:

• Khi ấn phím 1, nhân vật sẽ nói ra số ký tự có trong xâu đó
• Khi ấn phím 4, nhân vật sẽ nói ra số ký tự là chữ cái có trong xâu
• Khi ấn phím 3, nhân vật sẽ nói ra số ký tự là số có trong xâu
• Khi ấn phím 4, nhân vật sẽ nói ra số ký tự không phải là chữ cũng không phải là số có trong xâu

Gợi ý hướng giải quyết:

1. Dùng câu lệnh “length of … ” để đếm số ký tự trong xâu người dùng nhập vào
2. Tạo biến “số chữ cái” để lưu số lượng chữ cái có trong sâu. Tạo list “chữ cái” gồm 26 chữ cái trong bảng chữ cái tiếng anh. Duyệt từng ký tự trong xâu và kiểm tra xem ký tự đó có thuộc list chữ cái hay không. Nếu thuộc thì tăng giá trị của biến chữ cái lên 1 đơn vị
3. Tạo biến “số số” để lưu số lượng số có trong sâu. Tạo list “số” gồm 10 chữ số từ 0 đến 9. Duyệt từng ký tự trong xâu và kiểm tra xem ký tự đó có thuộc list “số” hay không. Nếu thuộc thì tăng giá trị của biến c”số số” lên 1 đơn vị
4. Tạo biến “số ký tự đặc biệt” để lưu số lượng số ký tự đặc biệt có trong sâu. Duyệt từng ký tự trong xâu và kiểm tra xem ký tự đó có không thuộc cả list “chữ cái” và list “số” hay không. Nếu không thuộc cả hai thì tăng giá trị của biến c”số ký tự đặc biệt” lên 1 đơn vị

Bài giải:

Link project: https://scratch.mit.edu/projects/408533906/

Bài 2: Xóa một loại ký tự nào đó trong xâu

Nhân vật sẽ yêu cầu người chơi nhập vào một sâu bất kỳ. Chương trình sẽ xóa bỏ mọi ký tự không phải là chữ trong xâu đó. Sau đó nhân vật sẽ thông báo xâu kết quả ra màn hình.

Gợi ý hướng giải quyết:

Scratch không có câu lệnh xóa một ký tự nào đó trong xâu. Do đó ta sẽ phải tạo ra một biến để lưu xâu mới. Tất cả các ký tự trong xâu cũ thỏa mãn điều kiện sẽ được thêm vào xâu mới. Cụ thể:

• Tạo list “chữ cái” gồm 26 chữ cái trong bảng chữ cái tiếng anh.
• Duyệt từng ký tự trong xâu và kiểm tra xem ký tự đó có thuộc list chữ cái hay không. Nếu thuộc thì nối nó vào biến chứa xâu mới

Bài giải:

Link project: https://scratch.mit.edu/projects/408544408/

Lưu ý: Nếu đề bài cho là xóa ký tự chữ hoặc xóa ký tự đặc biệt thì ta cũng làm tương tự. Hướng làm chung là tìm các ký tự thỏa mãn yêu cầu của đề bài rồi nối vào xâu mới.

Bài 3: Xóa ký tự trùng trong xâu

Nhân vật sẽ yêu cầu người dùng nhập một xâu bất kỳ từ bàn phím.

Sau đó, chương trình sẽ kiểm tra nếu thấy có 2 ký tự liền nhau và giống nhau thì xóa đi một ký tự.

Ví dụ nhập vào là aaxbbbccccd thì đưa ra kết quả axbcd

Gợi ý hướng giải quyết:

Bài tập này có ý tưởng giải quyết tương tự như bài 2 – xóa một loại ký tự nào đó trong xâu. Tuy nhiên, thay vì so sánh từng ký tự với danh sách chữ cái và danh sách số thì ta cần so sanh ký tự đang xét với ký tự phía trước nó để xem có trùng không. Nếu không trùng thì ta thêm ký tự đó vào xâu kết quả.

Xâu (string) xuất hiện rất nhiều trong các bài toán. Bài viết này giới thiệu sơ qua một số thuật ngữ cũng như thuật toán về xâu.

Thuật ngữ

• Một xâu $X$ là xâu con (substring) của một xâu $Y$ nếu $X$ là một chuỗi các ký tự liên tiếp của $Y$. Ví dụ: ab và bc là 2 xâu con của abcd. Nhưng ac thì không phải là xâu con của abcd.
• Một xâu $X$ là tiền tố (prefix) của một xâu $Y$ nếu $X$ là xâu con của $Y$ và $X$ xuất hiện ở đầu của xâu $Y$. Ví dụ: ab là tiền tố của abcd, nhưng bc không phải là tiền tố của abcd. Một xâu $X$ là một tiền tố không tầm thường (proper prefix) của xâu $Y$ nếu nó là tiền tố của xâu $Y$ và khác xâu $Y$.
• Một xâu $X$ là hậu tố (hậu tố) của một xâu $Y$ nếu $X$ là xâu con của $Y$ và $X$ xuất hiện ở cuối của xâu $Y$. Ví dụ: const char DUMMY = '.'; int manacher(string s) { // Để tránh phải xét riêng trường hợp độ dài xâu đối xứng chẵn / lẻ, // ta thêm 1 ký tự DUMMY vào giữa các ký tự của s. // CHÚ Ý: Phải đảm bảo DUMMY không có trong xâu s int n = s.size() 2 - 1;

  vector f = vector (n, 0); // Tạo xâu a bằng cách chèn ký tự DUMMY vào giữa các ký tự của s. // Ví dụ: // s = aabcb // a = a.a.b.c.b string a = string(n, DUMMY); for (int i = 0; i < n; i += 2) a[i] = s[i / 2]; int l = 0, r = -1, center, res = 0; for (int i = 0, j = 0; i < n; i++) {

  j = (i > r ? 0 : min(f[l + r - i], r - i)) + 1;  
  while (i - j >= 0 && i + j < n && a[i - j] == a[i + j]) j++;  
  f[i] = --j;  
  if (i + j > r) {  
    r = i + j;  
    l = i - j;  
  }  
  int len = (f[i] + i % 2) / 2  2 + 1 - i % 2;  
  if (len > res) {  
    res = len;  
    center = i;  
  }  
  

  } // Với mỗi vị trí i, xâu đối xứng dài nhất nhận i là tâm là [i - f[i], i + f[i]]. // Ví dụ: // s = aabcb // a = a.a.b.c.b // f = 011010200 return res; }
  3 là hậu tố của abcd, nhưng bc không phải là hậu tố của abcd. Một xâu $X$ là một hậu tố không tầm thường (proper suffix) của xâu $Y$ nếu nó là hậu tố của xâu $Y$ và khác xâu $Y$.

Các dạng bài

So khớp chuỗi (string matching)

Cho một xâu $T$ và xâu $S$. Tìm tất cả các lần xuất hiện của xâu $S$ trong xâu $T$.

Ví dụ:

S = abc
T = abcabcabc
Các lần xuất hiện: 1, 4, 7.

Bài toán này còn được gọi là tìm kiếm cây kim (needle) trong đống rơm (haystack), vì nó xuất hiện trong thực tế khi ta cần tìm một xâu rất nhỏ trong một lượng dữ liệu rất lớn (ví dụ Google cần tìm từ khóa trong hàng tỉ tỉ trang web).

Có 3 thuật toán chính để giải quyết bài này, đó là:

• Thuật toán KMP
• Hash
• Z Algorithm

Xâu đối xứng (Palindrome)

Palindrome hay còn gọi là xâu đối xứng, xâu đối gương là tên gọi của những xâu kí tự mà khi viết từ phải qua trái hay từ trái qua phải thì xâu đó không thay đổi. VD: MADAM, IOI,…

Có rất nhiều bài tập liên quan đến xâu đối xứng. Các bạn có thể tìm đọc ở trong các bài viết:

• Một vài bài tập QHD về Palindrome
• Hash
• Palindrome Tree

Cấu trúc dữ liệu

• Trie là CTDL cơ bản nhất trong xử lý xâu. Nó giúp giải quyết các bài toán về tìm kiếm xâu.
• Lớp CTDL được gọi chung là Suffix Structures gồm:
  • Suffix Array
  • Suffix Automaton
  • Suffix Tree
  • Aho Corasick Gọi chung như vậy vì các CTDL này có thể dùng thay thế nhau để giải quyết cùng một lớp bài toán liên quan đến các suffix của cây.

Các bài Ad-hoc

Trong xử lý xâu còn một vài thuật toán chỉ áp dụng được cho 1 bài toán (ad-hoc).

Thuật toán Manacher

Bài toán

Cho xâu $S$.

• Với mỗi vị trí $i$ của xâu $S$, tìm xâu đối xứng dài nhất nhận $i$ là tâm.
• Với mỗi cặp $i$, $i+1$ của xâu $S$, tìm xâu đối xứng dài nhất nhận $i$ và $i+1$ là tâm.

Mô tả thuật toán

Tham khảo thêm ở link

Code

const char DUMMY = '.';
int manacher(string s) {
  // Để tránh phải xét riêng trường hợp độ dài xâu đối xứng chẵn / lẻ,
  // ta thêm 1 ký tự DUMMY vào giữa các ký tự của s.
  // CHÚ Ý: Phải đảm bảo DUMMY không có trong xâu s
  int n = s.size() * 2 - 1;
  vector  f = vector (n, 0);
  // Tạo xâu a bằng cách chèn ký tự DUMMY vào giữa các ký tự của s.
  // Ví dụ:
  // s = aabcb
  // a = a.a.b.c.b
  string a = string(n, DUMMY);
  for (int i = 0; i < n; i += 2) a[i] = s[i / 2];
  int l = 0, r = -1, center, res = 0;
  for (int i = 0, j = 0; i < n; i++) {
    j = (i > r ? 0 : min(f[l + r - i], r - i)) + 1;
    while (i - j >= 0 && i + j < n && a[i - j] == a[i + j]) j++;
    f[i] = --j;
    if (i + j > r) {
      r = i + j;
      l = i - j;
    }
    int len = (f[i] + i % 2) / 2 * 2 + 1 - i % 2;
    if (len > res) {
      res = len;
      center = i;
    }
  }
  // Với mỗi vị trí i, xâu đối xứng dài nhất nhận i là tâm là [i - f[i], i + f[i]].
  // Ví dụ:
  // s = aabcb
  // a = a.a.b.c.b
  // f = 011010200
  return res;
}

Minimal string rotation

Bài toán

Cho một xâu $S$. Xét các xâu thu được từ xâu $S$ bằng phép xoay. Ví dụ:

const char DUMMY = '.';
int manacher(string s) {
  // Để tránh phải xét riêng trường hợp độ dài xâu đối xứng chẵn / lẻ,
  // ta thêm 1 ký tự DUMMY vào giữa các ký tự của s.
  // CHÚ Ý: Phải đảm bảo DUMMY không có trong xâu s
  int n = s.size() * 2 - 1;
  vector  f = vector (n, 0);
  // Tạo xâu a bằng cách chèn ký tự DUMMY vào giữa các ký tự của s.
  // Ví dụ:
  // s = aabcb
  // a = a.a.b.c.b
  string a = string(n, DUMMY);
  for (int i = 0; i < n; i += 2) a[i] = s[i / 2];
  int l = 0, r = -1, center, res = 0;
  for (int i = 0, j = 0; i < n; i++) {
    j = (i > r ? 0 : min(f[l + r - i], r - i)) + 1;
    while (i - j >= 0 && i + j < n && a[i - j] == a[i + j]) j++;
    f[i] = --j;
    if (i + j > r) {
      r = i + j;
      l = i - j;
    }
    int len = (f[i] + i % 2) / 2 * 2 + 1 - i % 2;
    if (len > res) {
      res = len;
      center = i;
    }
  }
  // Với mỗi vị trí i, xâu đối xứng dài nhất nhận i là tâm là [i - f[i], i + f[i]].
  // Ví dụ:
  // s = aabcb
  // a = a.a.b.c.b
  // f = 011010200
  return res;
}

7, thì các xâu thu được từ $S$ bằng phép xoay là:

• abcd
• const char DUMMY = '.'; int manacher(string s) { // Để tránh phải xét riêng trường hợp độ dài xâu đối xứng chẵn / lẻ, // ta thêm 1 ký tự DUMMY vào giữa các ký tự của s. // CHÚ Ý: Phải đảm bảo DUMMY không có trong xâu s int n = s.size() 2 - 1;

  vector f = vector (n, 0); // Tạo xâu a bằng cách chèn ký tự DUMMY vào giữa các ký tự của s. // Ví dụ: // s = aabcb // a = a.a.b.c.b string a = string(n, DUMMY); for (int i = 0; i < n; i += 2) a[i] = s[i / 2]; int l = 0, r = -1, center, res = 0; for (int i = 0, j = 0; i < n; i++) {

  j = (i > r ? 0 : min(f[l + r - i], r - i)) + 1;  
  while (i - j >= 0 && i + j < n && a[i - j] == a[i + j]) j++;  
  f[i] = --j;  
  if (i + j > r) {  
    r = i + j;  
    l = i - j;  
  }  
  int len = (f[i] + i % 2) / 2  2 + 1 - i % 2;  
  if (len > res) {  
    res = len;  
    center = i;  
  }  
  

  } // Với mỗi vị trí i, xâu đối xứng dài nhất nhận i là tâm là [i - f[i], i + f[i]]. // Ví dụ: // s = aabcb // a = a.a.b.c.b // f = 011010200 return res; }
  9
• // Tính vị trí của xâu xoay vòng có thứ tự từ điển nhỏ nhất của xâu s[] int minmove(string s) { int n = s.length(); int x, y, i, j, u, v; // x is the smallest string before string y for (x = 0, y = 1; y < n; y) {

  i = u = x;  
  j = v = y;  
  while (s[i] == s[j]) {  
     u;  v;  
    if ( i == n) i = 0;  
    if (++ j == n) j = 0;  
    if (i == x) break; // All strings are equal  
  }  
  if (s[i] <= s[j]) y = v;  
  else {  
    x = y;  
    if (u > y) y = u;  
  }  
  

  }

  return x; }

  0
• // Tính vị trí của xâu xoay vòng có thứ tự từ điển nhỏ nhất của xâu s[] int minmove(string s) { int n = s.length(); int x, y, i, j, u, v; // x is the smallest string before string y for (x = 0, y = 1; y < n; y) {

  i = u = x;  
  j = v = y;  
  while (s[i] == s[j]) {  
     u;  v;  
    if ( i == n) i = 0;  
    if (++ j == n) j = 0;  
    if (i == x) break; // All strings are equal  
  }  
  if (s[i] <= s[j]) y = v;  
  else {  
    x = y;  
    if (u > y) y = u;  
  }  
  

  }

  return x; }

  1

Tìm xâu có thứ tự từ điển nhỏ nhất.

Mô tả thuật toán

Bạn có thể xem ở đây

Code

// Tính vị trí của xâu xoay vòng có thứ tự từ điển nhỏ nhất của xâu s[]
int minmove(string s) {
  int n = s.length();
  int x, y, i, j, u, v; // x is the smallest string before string y
  for (x = 0, y = 1; y < n; ++ y) {
    i = u = x;
    j = v = y;
    while (s[i] == s[j]) {
      ++ u; ++ v;
      if (++ i == n) i = 0;
      if (++ j == n) j = 0;
      if (i == x) break; // All strings are equal
    }
    if (s[i] <= s[j]) y = v;
    else {
      x = y;
      if (u > y) y = u;
    }
  }
  return x;
}

Lyndon Decomposition

Bài toán

Lyndon word là các xâu khác rỗng, mà có thứ tự từ điển nhỏ hơn tất cả các xâu thu được bằng phép xoay của nó.