C++ หาจำนวนซับสตริงของสตริง

ในบทความนี้ คุณจะเรียนรู้วิธีการหาจำนวนซับสตริง (ไม่รวมสตริงว่าง) ที่สามารถสร้างได้จากสตริงที่กำหนด

Input : string = "moon" Output : 10 Explanation: ซับสตริงคือ 'm', 'o', 'o', 'n', 'mo', 'oo', 'on', 'moo', 'oon' และ 'moon'
Input : string = "yellow" Output : 21

วิธีการแก้ปัญหา

ให้ความยาวสตริง = n จากตัวอย่าง เราเข้าใจว่าต้องบวกซับสตริงความยาว n, (n-1), (n-2), ..., 2, 1

จำนวนซับสตริงทั้งหมด = n + (n - 1) + (n - 2) + ... + 2 + 1

= n * (n + 1) / 2

ตอนนี้เรามีสูตรคำนวณจำนวนซับสตริง โดย n คือความยาวสตริง

โค้ด C++ สำหรับวิธีการข้างต้น

นี่คือโค้ด C++ ที่ใช้แก้ปัญหานี้

ตัวอย่าง

#include<bits/stdc++.h> 
using namespace std; 

int main () { 
    string str = "yellow"; 
    int n = str.length (); 
    int number_of_strings = n * (n + 1) / 2; 
    cout << "Number of substrings of a string : " << number_of_strings; 
    return 0; 
}

ผลลัพธ์

Number of substrings of a string: 21

คำอธิบายโค้ด

นี่คือวิธีที่ง่ายและมีประสิทธิภาพที่สุดในการหาจำนวนซับสตริงที่เป็นไปได้จากสตริงที่กำหนด

ในโค้ดนี้ เราหาความยาวสตริงจากฟังก์ชัน .length() นำค่านั้นไปแทนในสูตรที่เราได้มาข้างต้น แล้วพิมพ์ผลลัพธ์จากตัวแปร result

สรุป

ในบทความนี้ เราอธิบายวิธีหาจำนวนซับสตริงในสตริง โดยเริ่มจากสร้างสูตรหาจำนวนซับสตริงทั้งหมดที่เป็นไปได้ แล้วคำนวณผลลัพธ์จากความยาวสตริง สามารถเขียนโปรแกรมเดียวกันในภาษาอื่น เช่น C, Java, Python ได้ หวังว่าจะเป็นประโยชน์