ค้นหาดัชนีเริ่มต้นของสตริงย่อยในสตริง (S) ซึ่งสร้างโดยการต่อคำทั้งหมดจากรายการ (L) ใน C ++

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

ดังนั้นหากอินพุตเป็นเหมือน “wordgoodgoodgoodword” และคำเป็น ["word","good"] ผลลัพธ์จะเป็น [0,12] เนื่องจากสตริงย่อยที่เริ่มต้นที่ดัชนี 0 และ 12 คือ “wordgood” และ “goodword”

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดวิธีการที่เรียกว่า ok() ซึ่งจะใช้สตริง s, แมป wordCnt และ n -

• ทำสำเนาของ s เป็น temp

• สำหรับฉันอยู่ในช่วง n ถึงขนาดของ s – 1

  • ถ้าขนาดของอุณหภูมิหลายเท่าของ 0 แล้ว

    • หากเมื่อไม่มี temp ใน wordCnt ให้คืนค่าเท็จ

    • อย่างอื่น

      • ถ้า wordCnt[temp] เป็น 1 ให้ลบ temp ออกจาก wordCnt ให้ตั้งค่า temp เป็นสตริงว่าง

      • หรือลดค่าของ wordCnt[temp] ลง 1 ตั้งค่า temp เป็นสตริงว่าง

  • เพิ่มอุณหภูมิโดย s[i]

• หาก temp ไม่ได้อยู่ใน wordCnt ให้คืนค่าเท็จ

• อย่างอื่น

  • ถ้า wordCnt[temp] เป็น 1 ให้ลบ temp ออกจาก wordCnt ให้ตั้งค่า temp เป็นสตริงว่าง

  • หรือลดค่าของ wordCnt[temp] ลง 1 ตั้งค่า temp เป็นสตริงว่าง

• คืนค่าจริงเมื่อขนาดของ wordCnt เป็น 0

• จากวิธีหลัก ทำสิ่งนี้

• ถ้าขนาดของ a เป็น 0 หรือขนาดของ b เป็น 0 ให้คืนค่าอาร์เรย์ว่าง

• ทำแผนที่ wordCnt เก็บความถี่ของสตริงที่มีอยู่ใน b เป็น wordCnt

• สร้างอาร์เรย์ที่เรียกว่า ans

• window :=จำนวนคำ x จำนวนตัวอักษรในแต่ละคำ

• สร้างสำเนาของสตริง a เป็น temp

• สำหรับฉันในหน้าต่างช่วงขนาด – 1

  • ถ้าขนาด temp ถูกหารด้วยหน้าต่างและเรียก ok(temp, wordCnt, size of b[0]) แล้ว

    • ใส่ i – window เข้าไปใน ans

  • ใส่ a[i] ลงใน temp

  • ถ้าขนาดของ temp> window ให้ลบ substring จาก 0, 1

• ถ้าขนาด temp ถูกหารด้วยหน้าต่างและเรียก ok(temp, wordCnt, size of b[0]) แล้ว

  • แทรกขนาดของหน้าต่าง a ลงใน 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;
   }
};
main(){
   vector<string> v = {"word","good"};
   Solution ob;
   print_vector(ob.findSubstring("wordgoodgoodgoodword", v));
}

อินพุต

“wordgoodgoodgoodword”, {"word","good"}

ผลลัพธ์

[0, 12, ]