Codeforces ECR #021 : G. Anthem of Berland

これは割と綺麗に解けた気がする。
http://codeforces.com/contest/808/problem/G

問題

2つの文字列S,Tがある。
Sは一部の文字がワイルドカードとなっている。
ワイルドカードを最適に別の文字に置き換えたとき、最大でsubstringとしてTをいくつ含むか。

解法

Editorialとは別解法。

以下の状態を考え、DPで後ろから埋めていこう。解はmax(f(0),g(0))となる。
f(i) := S[i]文字目以降にTのsubstringを最大いくつ含むか。ただしS[i..(|T|-1-i)]はTと一致しない
g(i) := S[i]文字目以降にTのsubstringを最大いくつ含むか。ただしS[i..(|T|-1-i)]はTと一致する。

f(i)=max(f(i+1),g(i+1))は自明。問題はg(i)である。

まず、S[i..(|T|-1-i)]がTと一致できるかどうかワイルドカードを含め判定しよう。
この時点で一致しない場合、g(i)=f(i)である。(以下のコード中では-infとしているがまぁ問題ない)

iの次に、S[j..(|T|-1-j)]=Tとなるjがi＜j＜i+|T|の範囲にあったと仮定する。
その場合、g(i)=g(j)+1となるが、その場合Tの末尾|T|-(j-i)文字とS[j..(|T|-1-j)]=Tの先頭|T|-(j-i)文字が一致しなければならない。
この判定は、EditorialのようにKMPで行ってもよいし、以下のコードのようにZ-algorithmで行ってもよい。

今回の問題は|S|*|T|≦10^7なので、各iに対し、i＜j＜i+|T|となるjを総当たりしても間に合う。

string S,T;
int NS,NT;

int ma[101010][2];

vector<int> Zalgo(string s) {
	vector<int> v(1,s.size());
	for(int i=1,l=-1,r=-1;i<s.size();i++) {
		if(i<=r && v[i-l]<r-i+1) v.push_back(v[i-l]);
		else {
			l=i; r=(i>r)?i:(r+1);
			while(r<s.size() && s[r-i]==s[r]) r++;
			v.push_back((r--)-l);
		}
	}
	v.push_back(0);
	return v;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>T;
	NS=S.size();
	NT=T.size();
	
	vector<int> V=Zalgo(T);
	
	int ret=0;
	for(i=NS-NT;i>=0;i--) {
		ma[i][0]=max(ma[i+1][0],ma[i+1][1]);
		int hoge=max(ma[i+NT][0],ma[i+NT][1]);
		FOR(x,NT) {
			if(S[i+x]!='?' && S[i+x]!=T[x]) break;
			if(x && V[x]+x==NT) hoge=max(hoge,ma[i+x][1]);
		}
		if(x==NT) {
			ma[i][1]=1+hoge;
		}
		else {
			ma[i][1]=-1<<30;
		}
		ret=max({ret,ma[i][0],ma[i][1]});
	}
	cout<<ret<<endl;
	
}

まとめ

ちょっと入力サイズにヒントが多すぎたね。