[Chuỗi] – Các thuật toán cơ bản về Chuỗi

Chuỗi về cơ bản nó là một mảng một chiều mà các phần tử là các ký tự. Tuy nhiên, chuỗi có một số bài toán đặc thù mà bạn hay gặp như:

  • Tìm một ký tự trong chuỗi
  • Đếm số ký tự trong chuỗi
  • Tìm một chuỗi con trong một chuỗi
  • Đảo ngược chuỗi
  • Tách chuỗi

Đây là các bài toán thường gặp, với hy vọng sẽ giúp bạn tự tin hơn khi làm việc với chuỗi.

Bài 1: Viết chương trình khởi tạo một chuỗi, sau đó nhập vào một ký tự c rồi đếm số lần ký tự c xuất hiện trong chuỗi.

Phân tích và tìm cách giải

  • Đầu vào: s=”IVIETTECH”, giá trị c
  • Đầu ra: In ra thông báo số lần c xuất hiện trong chuỗi
  • Phân tích:
    • Nhập vào ký tự c
    • Khởi tạo biến đến count=0
    • Duyệt qua chuỗi s và tăng count lên 1 mỗi khi gặp chuỗi c

Cách biểu diễn thuật toán

Trong trường hợp này, tôi sử dụng ngôn ngữ giả.

Declare   String s=”IVIETTECH”

char c

int count=0

Input c

Loop i=0 to s.lengh -1

   If(c=s[i] Or upper(c)=s[i])

      Count=count +1

If coun>0

   Print c + ‘xuat hien ’ + count + ‘ lan trong chuoi ’ + s

Else

   Print c + ‘ khong co trong chuoi trong chuoi’ + s

 Yêu cầu mở rộng bài toán trên

Bạn thay đổi chương trình trên để có thể đếm số ký tự  trong chuỗi và in ra số lần xuất hiện của các ký tự trong chuỗi đó.

Ví dụ: s={IVIETTECH}

Kết quả in ra:

I – 2

V-1

E-2

T-2

C-1

H-1

Hướng dẫn

  • Viết một hàm nhận ký tự cần đếm và vị trí của ký tự đó. Ví dụ countChar(String s, char c, int i)
  • Trong đó:
    1. Lặp từ 0 -> đến i-1 nếu ký tự đó đã xuất hiện thì thoát khỏi hàm (đã đếm rồi).
    2. Lặp từ i đến cuối chuỗi, đến số lần xuất hiện của ký tự đó
    3. In ký tự đó ra theo dạng c-count
  • Trong hàm main cho lặp từ đầu đến cuối chuỗi và gọi hàm countChar ở trên để đếm và in ra.

Bài tiếp: Thuật toán tìm chuỗi con

Bài trước: Thuật toán đổ dữ liệu về mảng một chiều và ngược lại

Đối tác tuyển dụng