สตริงย่อยที่เป็นการต่อเนื่องของทุกคำใน C++

สมมติว่าเรามีสตริง s และรายการคำ words ซึ่งคำทุกคำมีความยาวเท่ากัน เราต้องหาดัชนีเริ่มต้นทั้งหมดของสตริงย่อยใน s ที่เป็นการต่อเนื่องของคำใน words ทุกคำพอดีหนึ่งครั้ง และไม่มีตัวอักษรอื่นแทรกแซง

เช่น ถ้าอินพุตคือ "barfoothefoobarman" และ words = ["foo", "bar"] ผลลัพธ์จะเป็น [0,9] เพราะสตริงย่อยที่เริ่มต้นดัชนี 0 และ 9 คือ "barfoo" และ "foobar"

ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:

• กำหนดฟังก์ชัน ok() รับ s, map wordCnt, n
• ทำงานกับสตริงชั่วคราว temp ตรวจสอบทุกคำที่มีความยาว n
• จาก main method: ถ้า a หรือ b ว่าง คืนค่าอาร์เรย์ว่าง สร้าง map wordCnt นับความถี่คำใน b
• window := จำนวนคำ x ความยาวแต่ละคำ
• เลื่อน sliding window ตรวจสอบแต่ละตำแหน่ง เรียก ok() เพื่อยืนยัน
• เก็บดัชนีที่ผ่านเกณฑ์ลงใน ans คืนค่า ans

ตัวอย่าง

ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector v){
    cout << "[";
    for(int i = 0; i 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.size() == 0 || b.size() == 0) return {};
        unordered_map wordCnt;
        for(int i = 0; i < b.size(); i++) wordCnt[b[i]]++;
        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;
    }
};
main(){
    vector v = {"foo", "bar"};
    Solution ob;
    print_vector(ob.findSubstring("barfoothefoobarman", v));
}

อินพุต

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

เอาต์พุต

[0, 9]