Cách tìm tất cả các chuỗi con của chuỗi đã cho trong C#

Trong bài viết này mình sẽ hướng dẫn các bạn cách tìm tất cả các chuỗi con của chuỗi đã cho trong C#. Đây là một bài tập có áp dụng thuật toán logic, vì vậy hãy tìm hiểu thuật toán trước khi viết chương trình nhé.

1. Thuật toán tìm tất cả các chuỗi con của một chuỗi

Trước khi đi vào tìm hiểu thuật toán, chúng ta cùng xem qua một ví dụ đơn giản về các chuỗi con của một chuỗi đã cho.

Ví dụ: ta có chuỗi “ABC” thì tất cả các chuỗi con của chuỗi đã cho là: “A”, “AB”, “ABC”, “B”, “BC”, “C”.

Thuật toán:

Bài viết này được đăng tại [kiso.vn]

  1. Xác định một chuỗi.
  2. Vòng lăp đầu tiên (vòng lặp ngoài), lặp các ký tự của chuỗi đã cho.
  3. Vòng lặp hai (vòng lặp trong), xây dựng chuỗi con bằng cách thêm một ký tự sau mỗi vòng lặp cho đến khi hết chuỗi. Ví dụ: ta có chuỗi “ABC” thì vòng lặp đầu tiên sẽ là các vị trí A, B, C. Vòng lặp thứ hai sẽ kết hợp với vòng lặp thứ nhất A, AB, ABC rồi đến B, BC,…
  4. In chuỗi con.

2. Sử dụng phương pháp tiếp cận đơn giản trong C#

Trong ví dụ sau, mình sử dụng hai vòng lặp như thuật toán đã đưa ra ở trên. Vòng lặp bên ngoài để duy trì vị trí tương đối của ký tự đầu tiên. Và vòng lặp bên trong được sử dụng để tạo tất cả các chuỗi con có thể có. Sau đó in ra màn hình console.

*Lưu ý: Khai báo thư viện System.Text; trước khí sử dụng StringBuilder nhé.

using System;
using System.Linq;
using System.Text;
using System.Collections.Generic;
namespace ConsoleApp5
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Nhap vao mot chuoi: ");
            string inputString = Console.ReadLine();
            Console.WriteLine("Tat ca cac chuoi con: ");

            for (int i = 0; i < inputString.Length; ++i)
            {
                StringBuilder subString = new StringBuilder(inputString.Length - i);
                for (int j = i; j < inputString.Length; ++j)
                {
                    subString.Append(inputString[j]);
                    Console.Write(subString + " ");
                }
            }
            Console.WriteLine("n ----Chuong trinh nay duoc dang tai Kiso.vn---- n");
            Console.ReadKey();
        }
    }
}

Kết quả:

bai13 01 png

3. Sử dụng phương thức Substring() trong C#

Trong ví dụ dưới đây, mình sử dụng phương thức Substring() có sẵn trong C# để tạo chuỗi. Substring(i, length) tạo một chuỗi con có độ dài “length” bắt đầu từ chỉ mục i trong chuỗi đã cho.

using System;
using System.Linq;
using System.Text;
using System.Collections.Generic;
namespace ConsoleApp5
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Nhap vao mot chuoi: ");
            string inputString = Console.ReadLine();

            int len = inputString.Length;
            Console.WriteLine("Tat ca cac chuoi con: ");
            for (int i = 0; i < len; i++)
            {
                for (int j = 0; j < len - i; j++)
                {
                    Console.Write(inputString.Substring(i, j + 1) + " ");
                }
            }
            Console.WriteLine("n ----Chuong trinh nay duoc dang tai Kiso.vn---- n");
            Console.ReadKey();
        }
    }
}

Kết quả:

bai13 02 png

4. Sử dụng Linq trong C#

Trong ví dụ này mình sử dụng câu lệnh truy vấn Linq để tìm tất cả cá chuỗi con có thể có, cũng như các chuỗi duy nhất của một chuỗi nhất định.

using System;
using System.Linq;
using System.Text;
using System.Collections.Generic;
namespace ConsoleApp5
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Nhap vao mot chuoi: ");
            string inputString = Console.ReadLine();

            var Substrings =
                from i in Enumerable.Range(0, inputString.Length)
                from j in Enumerable.Range(0, inputString.Length - i + 1)
                where j >= 1
                select inputString.Substring(i, j);
            Console.WriteLine();
            Console.WriteLine("Tat ca cac chuoi con: ");
            foreach (string substring in Substrings)
            {
                Console.Write(substring + " ");
            }
            Console.WriteLine();
            Console.WriteLine();
            Console.WriteLine("Tat ca cac chuoi duy nhat: ");
            foreach (string substring in Substrings.Distinct())
            {
                Console.Write(substring + " ");
            }
            Console.WriteLine("n ----Chuong trinh nay duoc dang tai Kiso.vn---- n");
            Console.ReadKey();
        }
    }
}

Kết quả:

bai13 03 png

Như vậy là chúng ta đã thực hiện xong các chương trình để tìm tất cả các chuỗi con của một chuỗi đã cho trong C#. Các bạn hãy luyện tập thật nhiều để sử dụng nó thành thạo nhé, chúc các bạn thành công !!!

Bài viết liên quan

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *