Codeforces 138B (226B) Two Strings

問題

二つの文字列s, tが与えられる。
任意のiに対して、sのi番目の文字を含んだ、必ずしも連続しないsの部分文字列であって、
tに一致するものが存在するか。

存在するならYesを、そうでないならNoを出力せよ。

制約条件

s, tの長さ≦2 * 10^5
s, tは英小文字からなる

方針

sのi番目を含む部分文字列でtに一致するものが存在するかを、全てのiについて調べる。
ひとつのiに対するチェックの時間が短ければよい。

sのi番目より左側をtの左側からできるだけマッチさせる。この位置をrとする。
sのi番目より右側をtの右側からできるだけマッチさせる。この位置をlとする。

tの、[l-1, r-1]の範囲にs[i]が一つでも含まれていればよい。

l, rは最初にDPをしておけばよくて、
s[i]がtのある範囲にあるかは、文字ごとに累積和を計算しておけばよい。

ソースコード

const int MX = 200010;
string s, t;
int n, m;
int l[MX], r[MX], sum[MX][26];

int main(){
	cin >> s >> t;
	n = s.size();
	m = t.size();
	
	rep(i, n){
		r[i] = i ? r[i - 1] : -1;
		if(r[i] < m - 1 && t[r[i] + 1] == s[i]) r[i]++;
	}
	l[n] = m;
	for(int i = n - 1; i >= 0; i--){
		l[i] = l[i + 1];
		if(l[i] > 0 && t[l[i] - 1] == s[i]) l[i]--;
	}
	rep(i, m) rep(j, 26){
		sum[i + 1][j] = sum[i][j] + (t[i] == 'a' + j);
	}
	rep(i, n){
		int a = i ? min(m, r[i - 1] + 2) : 1;
		int b = max(0, l[i + 1] - 1);
		int c = s[i] - 'a';
		
		if(sum[a][c] - sum[b][c] <= 0){
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}