Codeforces ECR #178 : E. Unpleasant Strings

これも割とすんなり。
https://codeforces.com/contest/2104/problem/E

問題

文字列Sに対し、文字列Tが喜ばしいとは、TがSの部分列(不連続でもよい)であることを示す。

今文字列Sが与えられる。
ここでクエリとして文字列Tが与えられる。
Tの末尾に何文字か加え、喜ばしくないようにしたい。
最小何文字加えればよいか。

なお、使える文字はアルファベット小文字の先頭K種類に限る。

解法

f(n,c) := TがSのprefix n文字の部分列であるとき、Tにcを加えたものが、最短でSの何文字目と合致するか
g(n) := TがSのprefix n文字の部分列であるとき、最小あと何文字加えればTが喜ばしくなくなるか

前処理として上記を順に求めよう。
各クエリにおいては、f(n,c)を使ってTが最小でSのprefix 何文字の部分列となるかO(|T|)で判定できる。
その値がmの時、g(m)を答えればよい。

int N,K;
string S;
int Q;
int nex[1<<20][26];
int need[1<<20];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>S;
	FOR(i,K) {
		nex[N][i]=N;
	}
	FOR(j,K) {
		for(i=N-1;i>=0;i--) {
			nex[i][j]=nex[i+1][j];
			if(S[i]=='a'+j) nex[i][j]=i;
		}
	}
	need[N]=1;
	for(i=N-1;i>=0;i--) {
		need[i]=1<<20;
		FOR(j,K) need[i]=min(need[i],need[nex[i][j]+1]+1);
	}
	cin>>Q;
	while(Q--) {
		cin>>s;
		int cur=0;
		FORR(c,s) {
			if(cur<N) cur=nex[cur][c-'a']+1;
			else cur=N+1;
		}
		cout<<need[cur]<<endl;
	}
	
}

まとめ

7問回とは言え、ECRのEにしては易しめ。