LeetCode Weekly Contest 109 : 936. Stamping The Sequence

これまでの難易度8に比べると難しめ。
https://leetcode.com/contest/weekly-contest-109/problems/stamping-the-sequence/

問題

２つの文字列S,Tが与えられる。

T

マスの白マスが並んでおり、スタンプには

S

マス分のサイズで各マス文字が書かれている。

スタンプを押すと、スタンプがカバーする|S|文字分の領域が対応する文字で上書きされる。
スタンプは全体が|T|マスの範囲内にしか押せないものとする。

スタンプを何度か押して、|T|マス上に並んだ文字列がTと一致するようにできるか。
可能ならその手順を示せ。

解法

こういう問題の定番として、逆順に戻していくというものがある。

T

マスの各開始位置に対し、そこから

S

文字分のうちSと不一致かつ以後上書きされる見込みのないマスとその数を管理しよう。

以後上書きされるマスは、途中何を押してもよいことになる。

よって、該当するマスの数が0の開始位置があれば、そこから|S|文字スタンプを押す、というのを全マスカバーするまで繰り返す。
最後に上記手順を逆順にしたものが解。

bitset<1024> ok[1010];

class Solution {
public:
	vector<int> movesToStamp(string S, string T) {
		int num[1010]={};
		int did[1010]={};
		int fix[1010]={};
		vector<int> R;
		
		int NS=S.size();
		int NT=T.size();
		int i,j,k,x,y;
		FOR(i,NT-NS+1) {
			FOR(j,NS) {
				ok[i][j]=S[j]==T[i+j];
				num[i]+=ok[i][j];
			}
		}
		
		FOR(i,1000) {
			FOR(j,NT-NS+1) if(num[j]==NS && did[j]==0) {
				did[j]=1;
				R.push_back(j);
				FOR(x,NS) if(fix[j+x]==0) {
					fix[j+x]=1;
					FOR(y,NT-NS+1) {
						int l=j+x-y;
						if(l<0 || l>=NS) continue;
						if(ok[y][l]==0) {
							ok[y][l]=1;
							num[y]++;
						}
					}
				}
			}
		}
		
		FOR(i,NT-NS+1) if(did[i]==0) return {};
		reverse(ALL(R));
		return R;
		
	}
};

まとめ

後で上書きするので逆順で考える問題、AtCoderで見たけど忘れてしまった。