Substring with Concatenation of All Words ใน C++

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

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

ขั้นตอนการแก้ปัญหา

• กำหนดเมธอด ok() รับสตริง s, แมป wordCnt, และ n
• คัดลอก s ไปที่ temp
• for i ในช่วง n ถึงขนาดของ s – 1
  • ถ้าขนาดของ temp หาร n ลงตัว
    • ถ้า temp ไม่อยู่ใน wordCnt คืนค่า false
    • มิฉะนั้น
      • ถ้า wordCnt[temp] เป็น 1 ลบ temp ออกจาก wordCnt ตั้ง temp เป็นสตริงว่าง
      • มิฉะนั้นลดค่า wordCnt[temp] ลง 1 ตั้ง temp เป็นสตริงว่าง
  • เพิ่ม temp ด้วย s[i]
• ถ้า temp ไม่อยู่ใน wordCnt คืนค่า false
• มิฉะนั้น
  • ถ้า wordCnt[temp] เป็น 1 ลบ temp ออกจาก wordCnt ตั้ง temp เป็นสตริงว่าง
  • มิฉะนั้นลดค่า wordCnt[temp] ลง 1 ตั้ง temp เป็นสตริงว่าง
• คืนค่า true เมื่อขนาดของ wordCnt เป็น 0
• จากเมธอดหลัก
  • ถ้าขนาดของ a เป็น 0 หรือขนาดของ b เป็น 0 คืนค่าอาร์เรย์ว่าง
  • สร้างแมป wordCnt เก็บความถี่ของสตริงใน b
  • สร้างอาร์เรย์ ans
  • window := จำนวนคำ x จำนวนตัวอักษรในแต่ละคำ
  • คัดลอกสตริง a ไปที่ temp
  • for i ในช่วง window ถึงขนาดของ a – 1
    • ถ้าขนาด temp หาร window ลงตัว และ เรียก ok(temp, wordCnt, ขนาดของ b[0]) แล้ว
      • ใส่ i – window ลง ans
    • ใส่ a[i] ลง temp
    • ถ้าขนาด temp > window ลบ substring ตำแหน่ง 0, 1
  • ถ้าขนาด temp หาร window ลงตัว และ เรียก ok(temp, wordCnt, ขนาดของ b[0]) แล้ว
    • ใส่ ขนาดของ a – window ลง ans
  • คืนค่า ans

ตัวอย่างโค้ด C++

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

void print_vector(vector<auto> 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));
}

อินพุต

1,2,3,4,5,6,7 3

เอาต์พุต

[0, 9, ]