AtCoder ABC #257 (日鉄ソリューションズプログラミングコンテスト2022) : G - Prefix Concatenation

前半でグダついた回。
https://atcoder.jp/contests/abc257/tasks/abc257_g

問題

文字列S,Tが与えられる。
Sのprefixをいくつか連結してTを構築したい。
可能なら、最小いくつ連結すればよいか答えよ。

解法

以下を考えると、dp(|T|)が解となる。
dp(n) := Tのprefix n文字を構築するのに最小何個のSのprefixが必要か。ただし、構築不可ならinfとする。

dp(n)からの遷移を考える。Z-algorithmを使うと、Tの(n+1)文字目から最大何文字がSのprefixと一致するかがわかる。
この値をf(n+1)とすると、
1≦i≦f(n+1)に対し、dp(n+i)=min(dp(n+i),dp(n)+1)と状態遷移できる。

int A,B;
string S,T;

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;
}

vector<int> del[505050];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>T;
	A=S.size();
	B=T.size();
	S=S+"@"+T;
	
	vector<int> Z=Zalgo(S);
	
	multiset<int> M;
	M={0};
	del[0].push_back(0);
	FOR(i,B) if(M.size()) {
		x=*M.begin();
		y=Z[A+1+i];
		if(y>0) {
			M.insert(x+1);
			del[i+y].push_back(x+1);
		}
		FORR(e,del[i]) M.erase(M.find(e));
	}
	
	
	if(M.empty()) cout<<-1<<endl;
	else cout<<*M.begin()<<endl;
	
}

まとめ

こちらは割とすんなり。