C++のすべての単語を連結した部分文字列

文字列sがあり、単語のリストもあるとします。配列に存在する単語はすべて同じ長さです。 s内の部分文字列のすべての開始インデックスを見つける必要があります。これは、単語内の各単語を1回だけ連結したものであり、文字が介在することはありません。

したがって、入力が「barfoothefoobarman」のようで、単語が["foo"、 "bar"]の場合、出力は[0,9]になります。これは、インデックス0と9で始まる部分文字列が「barfoo」と「foobar」であるためです。

これを解決するには、次の手順に従います-

• ok（）というメソッドを定義します。これには、文字列s、マップwordCnt、およびn −

  が必要です。

• sのコピーをtempに作成します

• nからsのサイズまでの範囲のiの場合– 1

  • tempのサイズが0の倍数の場合、

    • wordCntにtempが存在しない場合は、falseを返します

    • それ以外の場合

      • wordCnt [temp]が1の場合、wordCntからtempを削除し、tempを空の文字列として設定します

      • それ以外の場合は、wordCnt [temp]の値を1減らし、tempを空の文字列として設定します。

  • 温度をs[i]

    上げる

• tempがwordCntにない場合は、falseを返します

• それ以外の場合

  • wordCnt [temp]が1の場合、wordCntからtempを削除し、tempを空の文字列として設定します

  • それ以外の場合は、wordCnt [temp]の値を1減らし、tempを空の文字列として設定します。

• wordCntのサイズが0の場合はtrueを返します

• メインの方法から、これを行います

• aのサイズが0の場合、またはbのサイズが0の場合は、空の配列を返します

• マップwordCntを作成し、bに存在する文字列の頻度をwordCntに格納します

• ans

  という配列を作成します

• window：=単語数x各単語の文字数

• 文字列aのコピーを1つ一時に作成します

• 範囲ウィンドウ内のiの場合– 1

  のサイズ

  • 一時サイズがウィンドウで割り切れ、ok（temp、wordCnt、size of b [0]）を呼び出す場合は、

    • i –ウィンドウをansに挿入

  • a[i]をtempに挿入します

  • temp> windowのサイズの場合、0、1から部分文字列を削除します

• 一時サイズがウィンドウで割り切れ、ok（temp、wordCnt、size of b [0]）を呼び出す場合は、

  • –ウィンドウのサイズをansに挿入

• ansを返す

例

理解を深めるために、次の実装を見てみましょう-

#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));
}

入力

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

出力

[0, 9, ]