C++でシーケンスをスタンプする

最初は、シーケンスはn'？'です。マーク（nはターゲット文字列の長さ）。小文字のスタンプもあります。

各ターンで、シーケンスの上にスタンプを配置し、内のすべての文字をそのスタンプの対応する文字に置き換えることができます。最大10*nターンすることができます。例として、最初のシーケンスが「?????」で、スタンプが「abc」であるとすると、最初に「abc ??」、「？abc？」、「??abc」のような文字列を作成できます。ターン。

シーケンスにスタンプを付けることができる場合は、各ターンで左端の文字がスタンプされているインデックスの配列を返します。それが不可能な場合は、空の配列を返します。したがって、シーケンスが「ababc」で、スタンプが「abc」の場合、答えは[0、2]のようになります。これは、「?????」のように形成できるためです。 ->「abc??」 ->「ababc」。

したがって、入力がstamp ="abcd"、target ="abcdbcd"のような場合、出力は[3,0]

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

• 配列retを定義する

• ok：=true

• n：=スタンプのサイズ

• tsz：=0

• okがゼロ以外の場合、実行-

  • ok：=false

  • x：=0

  • szの初期化：=スタンプのサイズ、sz> 0の場合、更新（szを1つ減らす）、実行-

    • 初期化i：=0の場合、i <=スタンプのサイズの場合、更新（iを1増やします）、実行-

      • newStamp：=長さiの「*」の文字列+インデックスitosz-1からのスタンプのサブ文字列+スタンプのサイズと同じサイズの「*」の文字列

      • pos：=ターゲット内のnewStampのインデックス

      • posがターゲットに存在する間、実行-

        • ok：=true

        • x：=x + sz

        • retの最後にposを挿入します

        • ターゲットを位置位置から位置+スタンプのサイズまで「*」で塗りつぶします。

        • pos：=ターゲット内のnewStampのインデックス

  • tsz：=tsz + x

• 配列を逆にするret

• return（tszがターゲットのサイズと同じ場合はret、それ以外の場合は1つの空白配列）

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

例

#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:
   vector<int> movesToStamp(string stamp, string target) {
      vector<int> ret;
      bool ok = true;
      int n = stamp.size();
      int tsz = 0;
      while (ok) {
         ok = false;
         int x = 0;
         for (int sz = stamp.size(); sz > 0; sz--) {
            for (int i = 0; i <= stamp.size() - sz; i++) {
               string newStamp = string(i, '*') +
               stamp.substr(i, sz) + string(stamp.size() - sz - i, '*');
               int pos = target.find(newStamp);
               while (pos != string::npos) {
                  ok = true;
                  x += sz;
                  ret.push_back(pos);
                  fill(target.begin() + pos, target.begin() +
                  pos + stamp.size(), '*');
                  pos = target.find(newStamp);
               }
            }
         }
         tsz += x;
      }
      reverse(ret.begin(), ret.end());
      return tsz == target.size() ? ret : vector<int>();
   }
};
main(){
   Solution ob;
   print_vector(ob.movesToStamp("abcd", "abcdbcd"));
}

入力

"abcd", "abcdbcd"

出力

[3, 0, ]