Editorial for pointstr: Điểm trên 1 chuỗi

Hiểu bài toán

Bài toán yêu cầu đếm số lần xuất hiện của chuỗi con "luyencode" trong một chuỗi S cho trước. Chuỗi S có độ dài N (1 ≤ N ≤ 30). Điểm được tính cho mỗi lần chuỗi "luyencode" xuất hiện. Ví dụ, với S = "luyencode.com", kết quả là 1 vì có một lần xuất hiện duy nhất.

Các cách tiếp cận

Cách Brute Force (Duyệt từng ký tự)

#include <stdio.h>
#include <string.h>

int main() {
    int n;
    scanf("%d", &n);
    char s[100];
    scanf("%s", s);

    int count = 0;
    const char *target = "luyencode";
    int len = strlen(target);

    for (int i = 0; i <= n - len; i++) {
        int match = 1;
        for (int j = 0; j < len; j++) {
            if (s[i + j] != target[j]) {
                match = 0;
                break;
            }
        }
        if (match) {
            count++;
        }
    }

    printf("%d", count);
    return 0;
}

• Time Complexity: O(N * M) (với M là độ dài từ 'luyencode', ~10^9~)
• Space Complexity: O(1)

Phương pháp này duyệt qua từng ký tự của chuỗi S. Tại mỗi vị trí, nó kiểm tra xem chuỗi con bắt đầu từ đó có khớp với "luyencode" hay không bằng cách so sánh từng ký tự một. Nếu khớp thì tăng biến đếm. Đây là cách tiếp cận trực quan nhất nhưng có độ phức tạp thời gian cao hơn so với dùng hàm có sẵn.

Cách Using Standard Library (strstr)

#include <stdio.h>
#include <string.h>

int main() {
    int n;
    scanf("%d", &n);
    char s[100];
    scanf("%s", s);

    int count = 0;
    char *ptr = s;
    char *target = "luyencode";

    while ((ptr = strstr(ptr, target)) != NULL) {
        count++;
        ptr++; // Hoặc ptr += strlen(target);
    }

    printf("%d", count);
    return 0;
}

• Time Complexity: O(N) (trung bình)
• Space Complexity: O(1)

Sử dụng hàm strstr từ thư viện <string.h>. Hàm này trả về con trỏ tới lần xuất hiện đầu tiên của chuỗi "luyencode". Vòng lặp while tiếp tục tìm kiếm từ vị trí tiếp theo (bằng cách tăng con trỏ) cho đến khi không còn tìm thấy. Đây là cách hiệu quả và thường được sử dụng trong lập trình thi đấu.

Cách Using String Matching (KMP Algorithm - Advanced)

// C++ implementation for reference
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    string pattern = "luyencode";

    // KMP Logic (simplified for demonstration)
    // Normally requires preprocessing pattern to create LPS array

    int count = 0;
    size_t pos = 0;
    while ((pos = s.find(pattern, pos)) != string::npos) {
        count++;
        pos += 1; // Move to next position
    }

    cout << count;
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(M) (where M is pattern length)

Trong khi các giải pháp trên sử dụng thư viện chuẩn, một giải pháp tổng quát hơn cho bài toán tìm kiếm xâu là thuật toán KMP (Knuth-Morris-Pratt). Mặc dù với độ dài N nhỏ (≤ 30) thì KMP là quá mức cần thiết, nhưng nó đảm bảo thời gian tuyến tính O(N) ngay cả với dữ liệu lớn. Tuy nhiên, do ràng buộc N rất nhỏ, giải pháp strstr là tối ưu và dễ nhất.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán chỉ yêu cầu đếm số lần xuất hiện của một từ c cụ thể, không phải là bài toán xử lý văn bản phức tạp.
• Với độ dài chuỗi rất nhỏ (N ≤ 30), hiệu năng không phải là vấn đề lớn, nhưng việc chọn đúng hàm library sẽ giúp code ngắn gọn và chính xác.
• Cần chú ý xử lý đầu vào (scanf, getchar) để tránh lỗi khoảng trắng.

Lỗi thường gặp

• Quên tăng con trỏ trong vòng lặp while khi dùng strstr sẽ dẫn đến vòng lặp vô hạn.
• Sử dụng scanf("%s") cho chuỗi có khoảng trắng (mặc dù đề bài chỉ cho phép chuỗi đơn, nhưng fgets an toàn hơn).
• Độ dài mảng char chưa đủ để chứa chuỗi kết thúc '\0'.