Codeforces ECR #085 : G. Substring Search

ゴリ押しがきいてしまう問題。
https://codeforces.com/contest/1334/problem/G

問題

2つの文字列S,Tが与えられる。
また、各アルファベットに対応する数値として1～26の順列P[i]が与えられる。

T中でi文字目を先頭とする|S|文字の部分文字列T'(i)を考える。
各iに対し、SとT'(i)が下記を満たすかどうかを判定せよ。

• 文字cに対し、F[c]をcがアルファベットの何文字目かを示す。
• SとT'(i)の各j文字目に対し、F[S[j]]=F[T'(i)[j]]またはP[F[S[j]]]=F[T'(i)[j]]である

解法

公式ではFFTを使うようだが、あいにくこれbitsetでゴリ押せる。
各iに対し、j文字目が各条件を満たすかをbitsetのshiftで一気に処理し、各jの結果の論理積をbitsetのandで判定する。

int P[26],Q[26];
string S,T;
bitset<204800> BS,BT[26];

int A,B;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,26) {
		cin>>P[i];
		P[i]--;
		Q[P[i]]=i;
	}
	cin>>S>>T;
	FORR(c,S) c-='a';
	FORR(c,T) c-='a';
	
	A=S.size();
	B=T.size();
	FOR(i,B) BT[T[i]][i]=BT[Q[T[i]]][i]=1;
	FOR(i,B-A+1) BS[i]=1;
	FOR(i,A) BS&=BT[S[i]]>>i;
	FOR(i,B-A+1) cout<<BS[i];
	cout<<endl;
	
}

まとめ

解を見てしまうと、何とも拍子抜けな問題。