Chuỗi con nối tiếp tất cả từ trong C++

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

Ví dụ: s = "barfoothefoobarman", words = ["foo", "bar"] → kết quả [0, 9] vì "barfoo" (từ 0) và "foobar" (từ 9).

Giải thuật

• Hàm ok(s, wordCnt, n): kiểm tra chuỗi s có chứa đúng các từ trong wordCnt không.
  • Lấy n ký tự đầu vào temp.
  • Duyệt từ n đến hết s: nếu độ dài temp chia hết n → kiểm tra temp có trong wordCnt, cập nhật tần suất.
  • Thêm s[i] vào temp.
  • Cuối cùng kiểm tra temp còn lại.
  • Trả về true nếu wordCnt rỗng.
• Từ main:
  • Nếu a hoặc b rỗng → trả về mảng rỗng.
  • Tạo map wordCnt đếm tần suất từ trong b.
  • window = số từ * độ dài mỗi từ.
  • Duyệt cửa sổ trượt kích thước window trên a, gọi ok() kiểm tra.

Ví dụ minh họa (C++)

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

void print_vector(vector<int> v) {
    cout << "[";
    for(int i = 0; i < v.size(); i++) cout << v[i] << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    bool ok(string s, unordered_map<string, int> wordCnt, int n) {
        string temp = "";
        for(int i = 0; i < n; i++) temp += s[i];
        for(int i = n; i < s.size(); i++) {
            if(temp.size() % n == 0) {
                if(wordCnt.find(temp) == wordCnt.end()) return false;
                else {
                    if(wordCnt[temp] == 1) { wordCnt.erase(temp); temp = ""; }
                    else { wordCnt[temp]--; temp = ""; }
                }
            }
            temp += s[i];
        }
        if(wordCnt.find(temp) == wordCnt.end()) return false;
        else {
            if(wordCnt[temp] == 1) { wordCnt.erase(temp); temp = ""; }
            else { wordCnt[temp]--; temp = ""; }
        }
        return wordCnt.size() == 0;
    }

    vector<int> findSubstring(string a, vector<string> &b) {
        if(a.size() == 0 || b.size() == 0) return {};
        unordered_map<string, int> wordCnt;
        for(int i = 0; i < b.size(); i++) wordCnt[b[i]]++;
        vector<int> ans;
        int window = b.size() * b[0].size();
        string temp = "";
        for(int i = 0; i < window; i++) temp += a[i];
        for(int i = window; i < a.size(); i++) {
            if(temp.size() % window == 0 && ok(temp, wordCnt, b[0].size())) {
                ans.push_back(i - window);
            }
            temp += a[i];
            if(temp.size() > window) temp.erase(0, 1);
        }
        if(temp.size() % window == 0 && ok(temp, wordCnt, b[0].size()))
            ans.push_back(a.size() - window);
        return ans;
    }
};

int main() {
    vector<string> v = {"foo", "bar"};
    Solution ob;
    print_vector(ob.findSubstring("barfoothefoobarman", v));
    return 0;
}

Đầu vào

"barfoothefoobarman" ["foo", "bar"]

Đầu ra

[0, 9]