นับ substring ที่ขึ้นต้นและลงท้ายด้วยสตริงกำหนดใน C++

บทนำ

โจทย์: กำหนดสตริงหลัก และสตริงเริ่มต้น (start) พร้อมสตริงสิ้นสุด (end) นับจำนวน substring ที่ ต่างกัน (distinct) ที่ขึ้นต้นด้วย start และลงท้ายด้วย end

ตัวอย่าง

str = "getmesomecoffee"
start = "m"
end = "e"
ผลลัพธ์: 6
Substrings: me, mesome, mesomemecoffe, mesomemecoffee, mecoffe, mecoffee


ขั้นตอนการแก้ปัญหา

หาตำแหน่งทั้งหมดที่ match กับ start และ end ในสตริงหลัก
ใช้ set เก็บ substring ที่เจอ (กันซ้ำ)
สำหรับแต่ละตำแหน่ง start: ขยายไปขวาจนเจอ end → เก็บ substring ลง set
นับขนาด set


ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;

int getSubstringsCount(string str, string start, string end) {
    int substrings_count = 0, str_length = str.size(), start_length = start.size(), end_length = end.size();
    int start_matches_index[str_length] = {0}, end_matches_index[str_length] = {0};
    for (int i = 0; i < str_length; i++) {
        if (str.substr(i, start_length) == start) {
            start_matches_index[i] = 1;
        }
        if (str.substr(i, end_length) == end) {
            end_matches_index[i] = 1;
        }
    }
    set<string> substrings;
    string current_substring = "";
    for (int i = 0; i < str_length; i++) {
        if (start_matches_index[i]) {
            for (int j = i; j < str_length; j++) {
                if (!end_matches_index[j]) {
                    current_substring += str[j];
                }
                if (end_matches_index[j]) {
                    current_substring += str.substr(j, end_length);
                    if (substrings.find(current_substring) == substrings.end()) {
                        substrings_count++;
                    }
                    substrings.insert(current_substring);
                }
            }
            current_substring = "";
        }
    }
    return substrings_count;
}

int main() {
    string str = "getmesomecoffee";
    string start = "m";
    string end = "e";
    cout << getSubstringsCount(str, start, end) << endl;
    return 0;
}


ผลลัพธ์
6

ความซับซ้อน
เวลา: O(n² × m) โดย n = ความยาวสตริง, m = ความยาว substring เฉลี่ย (เพราะ substr และ set operations) พื้นที่: O(n²) สำหรับ set

สรุป
ใช้ set กรอง substring ซ้ำ ได้คำตอบที่ถูกต้อง แต่อาจช้าสำหรับสตริงยาวมาก สามารถปรับปรุงด้วย Suffix Array/Automaton