จากปัญหาที่เราได้รับสตริง str เราต้องนับสตริงย่อยทั้งหมดในสตริงที่กำหนด สตริงย่อยคือสตริงที่เป็นส่วนหนึ่งของสตริงที่มีอยู่แล้วซึ่งอาจมีขนาดเล็กกว่าหรือเท่ากับสตริงที่มีอยู่
มาทำความเข้าใจปัญหาและวิธีแก้ปัญหาด้วยตัวอย่าง
ป้อนข้อมูล − str ="wxyz";
ผลผลิต − จำนวนสตริงย่อยที่แตกต่างกันคือ:10
คำอธิบาย − นับสตริงย่อยที่แตกต่างกันคือ −
wxyz, wxy, wx, w, xyz, xy, x, yz, y, z so their count is 10
ป้อนข้อมูล − str ="zzzz"
ผลผลิต − จำนวนสตริงย่อยที่แตกต่างกันคือ:4
คำอธิบาย − นับสตริงย่อยที่แตกต่างกันคือ −
zzzz, zzz, zz, z
แนวทางที่ใช้ในโปรแกรมด้านล่างดังนี้
-
รับสตริงสตริงเป็นอินพุต
-
ประกาศ unordered_set "myset" ที่ว่างเปล่า
-
วนรอบ i จาก 0 ย้าย 1 ขั้น จนกระทั่ง i น้อยกว่าขนาดของสตริง
-
ประกาศช่องว่างสตริงใหม่ "" (ว่าง)
-
วน j เริ่มจาก i ย้าย 1 ขั้นในแต่ละครั้ง จนกระทั่ง j น้อยกว่าขนาดของสตริง
-
เชื่อมค่าของช่องว่างในแต่ละขั้นตอนด้วย str[j]
-
เว้นวรรคใน myset
-
-
พิมพ์ขนาดของ str เป็นคำตอบ
ตัวอย่าง
#include<iostream>
#include<unordered_set>
using namespace std;
int main(){
string str = "aaaa";
unordered_set<string> myset;
int i, j;
for (i = 0; i < str.size(); ++i){
string space = "";
for (j = i; j < str.size(); ++j){
space = space + str[j];
myset.insert(space);
}
}
cout <<"count of distinct substring is: " <<str.size();
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น เราจะได้ผลลัพธ์ดังต่อไปนี้ -
count of distinct substring is: 4
