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

ภาพรวมปัญหา

ให้อาร์เรย์สตริง str[] และรูปแบบ pattern pat ต้องการนับสตริงใน str[] ที่ลงท้ายด้วย pat

ตัวอย่าง

Input: str[] = {"kittens", "hens", "deers", "dogs"}, pat = "ens"

Output: 2

คำอธิบาย: "kittens" และ "hens" ลงท้ายด้วย "ens"

Input: str[] = {"tickets", "wickets", "bats", "cricket"}, pat = "et"

Output: 1

คำอธิบาย: "wickets" ลงท้ายด้วย "et"

แนวทางแก้ปัญหา

1. ฟังก์ชัน endPattern(string str[], int n, string ptr)
2. วนลูปแต่ละสตริงใน str[]
3. เปรียบเทียบตัวอักษรท้ายของสตริงกับ pattern ย้อนกลับ
4. ถ้าตรงกันทุกตัวอักษร ให้เพิ่ม count

โค้ดตัวอย่าง (Manual Comparison)

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

int endPattern(string str[], int n, string ptr) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        string s = str[i];
        int slen = s.length();
        int plen = ptr.length();
        
        if (slen < plen) continue;
        
        bool match = true;
        for (int j = 0; j < plen; j++) {
            if (s[slen - plen + j] != ptr[j]) {
                match = false;
                break;
            }
        }
        if (match) count++;
    }
    return count;
}

int main() {
    string patrn = "pes";
    string str[] = {"stripes", "cars", "ripes", "pipes"};
    int N = 4;
    cout << "Strings that end with given pattern: " << endPattern(str, N, patrn);
    return 0;
}

ผลลัพธ์

Strings that end with given pattern: 3

วิธีที่ง่ายกว่า (ใช้ C++ string methods)

int endPattern_modern(string str[], int n, string ptr) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (str[i].size() >= ptr.size() && 
            str[i].substr(str[i].size() - ptr.size()) == ptr) {
            count++;
        }
    }
    return count;
}

// หรือใช้ ends_with (C++20)
int endPattern_cpp20(string str[], int n, string ptr) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (str[i].ends_with(ptr)) count++;
    }
    return count;
}

ความซับซ้อน

• เวลา: O(N × L) โดย L = ความยาว pattern
• พื้นที่: O(1)

การประยุกต์ใช้

เหมาะสำหรับการค้นหานามสกุลไฟล์, suffix matching, DNA sequence analysis ฯลฯ