Tìm chỉ số bắt đầu chuỗi con ghép từ danh sách từ trong C++

Cho chuỗi s và danh sách từ words (cùng độ dài). Tìm tất cả chỉ số bắt đầu của chuỗi con trong s là sự nối tiếp của tất cả từ trong words đúng một lần, không có ký tự xen giữa.

Ví dụ

s = "wordgoodgoodgoodword", words = ["word","good"]

Kết quả: [0, 12] (tại 0: "wordgood", tại 12: "goodword")

Thuật toán (Sliding Window + Hash Map)

• Độ dài từ: len = words[0].size().
• Cửa sổ trượt: window = len * words.size().
• Dùng unordered_map đếm tần suất từ.
• Kiểm tra mỗi cửa sổ bằng hàm helper ok().

Triển khai C++

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

class Solution {
public:
    bool ok(string s, unordered_map<string, int> wordCnt, int n) {
        string temp = s.substr(0, n);
        for (int i = n; i <= s.size(); i++) {
            if (temp.size() % n == 0) {
                if (!wordCnt.count(temp)) return false;
                if (--wordCnt[temp] == 0) wordCnt.erase(temp);
                temp.clear();
            }
            if (i < s.size()) temp += s[i];
        }
        return wordCnt.empty();
    }

    vector<int> findSubstring(string s, vector<string>& words) {
        if (s.empty() || words.empty()) return {};
        unordered_map<string, int> wordCnt;
        for (auto& w : words) wordCnt[w]++;
        
        int n = words[0].size(), window = n * words.size();
        vector<int> ans;
        string temp = s.substr(0, window);
        
        for (int i = window; i <= s.size(); i++) {
            if (temp.size() == window && ok(temp, wordCnt, n))
                ans.push_back(i - window);
            if (i < s.size()) {
                temp += s[i];
                if (temp.size() > window) temp.erase(0, 1);
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<string> v = {"word","good"};
    auto res = ob.findSubstring("wordgoodgoodgoodword", v);
    for (int x : res) cout << x << " ";
    return 0;
}

Kết quả

0 12

Độ phức tạp: O(N * L) với N = độ dài s, L = độ dài từ.