Trong bài viết này, bạn sẽ tìm hiểu về các phương pháp để tìm số chuỗi con (không rỗng) mà bạn có thể tạo trong một chuỗi nhất định.
Input : string = “moon” Output : 10 Explanation: Substrings are ‘m’, ‘o’, ‘o’, ‘n’, ‘mo’, ‘oo’, ‘on’, ‘moo’, ‘oon’ and ‘moon’. Input : string = “yellow” Output : 21
Phương pháp tiếp cận để tìm ra giải pháp
Cho độ dài của chuỗi là n, vì vậy nhìn vào ví dụ trên, chúng ta hiểu rằng để tìm tất cả các chuỗi con có thể có, chúng ta cần thêm các chuỗi con có độ dài n, (n-1), (n-2), (n -3), (n-4), ...... 2, 1.
Tổng số chuỗi con =n + (n - 1) + (n - 2) + (n - 3) + (n - 4) + ……. + 2 + 1.
=n * (n + 1) / 2
Vì vậy, bây giờ chúng ta có một công thức để đánh giá số lượng chuỗi con trong đó n là độ dài của một chuỗi nhất định.
Mã C ++ cho cách tiếp cận trên
Đây là cú pháp C ++ mà chúng ta có thể sử dụng làm đầu vào để giải quyết vấn đề đã cho -
Ví dụ
#include<bits/stdc++.h>
using namespace std;
int main () {
string str = "yellow";
// finding the length of string
int n = str.length ();
// calculating result from formula
int number_of_strings = n * (n + 1) / 2;
cout << "Number of substrings of a string : " << number_of_strings;
return 0;
} Đầu ra
Number of substrings of a string: 21
Giải thích về Quy tắc
Đây là cách tiếp cận lạc quan và đơn giản để tìm số lượng các chuỗi con có thể có từ một chuỗi nhất định.
Đầu tiên, trong đoạn mã này, chúng ta tìm độ dài của một chuỗi nhất định từ hàm .length () và đặt giá trị đó vào công thức mà chúng ta đã suy ra ở trên, in kết quả được lưu trữ trong biến kết quả.
Kết luận
Trong bài viết này, chúng tôi đã giải thích cách tìm số chuỗi con trong một chuỗi, nơi đầu tiên chúng tôi suy ra công thức để tìm số lượng tất cả các chuỗi con có thể có và lấy kết quả bằng công thức từ độ dài của chuỗi. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.