C++ Tìm số chuỗi con của chuỗi này xuất hiện trong chuỗi kia

Cho hai chuỗi, đếm số chuỗi con của chuỗi 1 xuất hiện trong chuỗi 2 (chuỗi con giống nhau có thể xuất hiện nhiều lần). Ví dụ:

Input: string1 = "fogl", string2 = "google" → Output: 6
Chuỗi con: "o", "g", "l", "og", "gl", "ogl"

Input: string1 = "ajva", string2 = "java" → Output: 5
Chuỗi con: "a", "j", "v", "a", "va"

Phương pháp giải

Sinh tất cả chuỗi con của string1, kiểm tra từng chuỗi có tồn tại trong string2 không (dùng find), nếu có thì tăng bộ đếm.

Ví dụ minh họa

#include <iostream>
#include <string>
using namespace std;

int main() {
    string str1 = "ajva";
    string str2 = "java";
    int count = 0;
    int n = str1.length();

    for (int i = 0; i < n; i++) {
        string str3;
        for (int j = i; j < n; j++) {
            str3 += str1[j];
            if (str2.find(str3) != string::npos)
                count++;
        }
    }
    cout << "Số chuỗi con của chuỗi 1 có trong chuỗi 2: " << count;
    return 0;
}

Kết quả

Số chuỗi con của chuỗi 1 có trong chuỗi 2: 5

Giải thích mã

Duyệt i từ 0 đến n-1, j từ i đến n-1 để sinh chuỗi con str3. Kiểm tra str2.find(str3), nếu tìm thấy thì tăng count.

Kết luận

Giải pháp đơn giản đếm chuỗi con chung của hai chuỗi. Có thể viết bằng C, Java, Python. Hy vọng hữu ích.