Chuỗi con là nối của tất cả từ trong C++

Cho một chuỗi s và danh sách các 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 của từng từ trong words đúng một lần, không có ký tự can xen.

Ví dụ: s = "barfoothefoobarman", words = ["foo", "bar"] → Kết quả: [0, 9]. Chuỗi con tại 0 là "barfoo", tại 9 là "foobar".

Phương pháp giải

Sử dụng cửa sổ trượt và hàm kiểm tra ok(). Duyệt qua chuỗi s với cửa sổ có độ dài = số từ × độ dài mỗi từ. Kiểm tra xem chuỗi con trong cửa sổ có phải là hoán vị của words không.

Ví dụ chương trình

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

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

class Solution {
public:
    bool ok(string s, unordered_map 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 findSubstring(string a, vector& b) {
        if (a.empty() || b.empty()) return {};
        unordered_map wordCnt;
        for (string& w : b) wordCnt[w]++;
        
        vector 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 v = {"foo", "bar"};
    Solution ob;
    print_vector(ob.findSubstring("barfoothefoobarman", v));
    return 0;
}

Đầu vào

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

Đầu ra

[0, 9]