Chuỗi con với sự kết hợp của tất cả các từ trong C ++

Giả sử chúng ta có một chuỗi, s và chúng ta cũng có một danh sách các từ, các từ có trong mảng đều có cùng độ dài. Chúng ta phải tìm tất cả các chỉ số bắt đầu của (các) chuỗi con trong đó là sự ghép nối của mỗi từ trong các từ chính xác một lần và không có bất kỳ ký tự nào xen vào.

Vì vậy, nếu đầu vào giống như “barfoothefoobarman” và các từ là [“foo”, “bar”], thì đầu ra sẽ là [0,9]. Điều này là do chuỗi con bắt đầu từ chỉ mục 0 và 9 là “barfoo” và “foobar”.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một phương thức có tên ok (), phương thức này sẽ lấy chuỗi s, ánh xạ wordCnt và n -

• tạo một bản sao của s vào tạm thời

• cho tôi trong phạm vi n đến kích thước của s-1

  • nếu kích thước của nhiệt độ là bội số của 0, thì

    • nếu khi tạm thời không có trong wordCnt, thì trả về false

    • nếu không thì

      • nếu wordCnt [temp] là 1, thì xóa tạm thời khỏi wordCnt, đặt tạm thời là một chuỗi trống

      • nếu không, hãy giảm giá trị của wordCnt [temp] đi 1, đặt tạm thời là chuỗi trống.

  • tăng nhiệt độ lên s [i]

• nếu tạm thời không có trong wordCnt, thì trả về false

• nếu không thì

  • nếu wordCnt [temp] là 1, thì xóa tạm thời khỏi wordCnt, đặt tạm thời là một chuỗi trống

  • nếu không, hãy giảm giá trị của wordCnt [temp] đi 1, đặt tạm thời là chuỗi trống.

• trả về true khi kích thước của wordCnt là 0

• Từ phương thức chính, hãy thực hiện việc này

• nếu kích thước của a là 0 hoặc kích thước của b là 0, thì trả về mảng trống

• tạo bản đồ wordCnt, lưu trữ tần suất của các chuỗi có trong b vào wordCnt

• tạo một mảng được gọi là ans

• window:=số từ x số ký tự trong mỗi từ

• tạo một bản sao của chuỗi a thành tạm thời

• cho tôi trong phạm vi cửa sổ đến kích thước của a - 1

  • nếu kích thước tạm thời chia hết cho cửa sổ và gọi ok (tạm thời, wordCnt, kích thước của b [0]), thì

    • chèn i - window vào ans

  • chèn [i] vào tạm thời

  • if size of temp> window, sau đó xóa chuỗi con khỏi 0, 1

• nếu kích thước tạm thời chia hết cho cửa sổ và gọi ok (tạm thời, wordCnt, kích thước của b [0]), thì

  • chèn kích thước của a - window vào ans

• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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 = {"foo", "bar"};
   Solution ob;
   print_vector(ob.findSubstring("barfoothefoobarman", v));
}

Đầu vào

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

Đầu ra

[0, 9, ]